It doesn't seem to be a DNS or Traffic Shaping problem after all. The original machine I was noticing the problem on is a laptop (Thinkpad T43P) on a wireless connection (claiming 54Mbps speed at the time) and during playback I was only getting 1.5Mbps through the firewall. Then I tried a different and faster machine with wired Ethernet and it was able to play back not only at 720P, but 1080P and the traffic went up to 5.5Mpbs through the firewall. So then I tried sitting the T43P next to one of my wireless access points and wiring to it. I was able to play back 720P, but despite having network throughput it was not able to keep up with playing back 1080P. So then I switched back to wireless and was back down to 1.5Mpbs despite network status showing 100% signal on a 54Mbps wireless G connection.
So traffic shaping appears to be working and it's a specific client PC problem. I'll start chasing after updated drivers.