So far, the Token Bucket algorithm is doing an excellent job of keeping the bandwidth rate near the desired rate (the r parameter in the algorithm).
However, it has taken a bit to get here. I choose a burst rate that was way too conservative. I ran across a suggested burst rate formula on Cisco's site; burst rate = r * 8 * 1.5 where r is the desired bit rate, 8 is selected because we're using bits (instead of bytes) and 1.5 represents seconds. They empirically determined this value.
My own measurements agree with their indication that Token Bucket will tend to underflow if the burst rate is too small.
At least so far it looks like we get the best results with a bucket that is initially 1/3rd full and an incrementer that adds tokens every 3 milliseconds.