If I've understood correctly, you're trying to limit your ingress traffic from your ISP by limiting egress traffic on your locally facing interface.
The packet loss you're seeing are probably to be expected, as dropped packets are (one of) TCPs way(s) of detecting congestion, and the way a router can signal congestion. It's also the only reasonable way your router can abide by the limitation you've given it via tc without breaking i.e. TCPs congestion avoidance. (tc does have facilities for using RED, although I don't know enough about this to tell you anything beyond it's existence).
Instead of shaping egress traffic on your inward facing interface, you could check out tc's ingress qdisc, attach it to the interface facing your ISP and a tc filter to police your ingress traffic. Packet loss will still occur, as it's probably the only viable way for your router to signal congestion.
For an example, see the LARTC cookbook entry "The Ultimate Traffic Conditioner", which among other things use tc's ingress qdisc.
eth0has the WAN ip. As only upload speed can be shaped, I use the above posted line oneth1which is the NAT interface. So I shape the download rate ofeth0by shaping the upload oneth1. – nixnotwin May 20 '11 at 17:13