I suspect, that you didn't load appropriate kernel modules. For example, in order to use CBQ qdisc you should load sch_cbq qdisc:
[HN]# modprobe sch_cbq
[HN]# tc qdisc add dev eth0 root handle 1: cbq avpkt 1000 bandwidth [HN]# tc qdisc show
qdisc cbq 1: dev eth0 rate 100000Kbit (bounded,isolated) prio no-transmit
HTH,
vass.