Check to see if your Airport Extreme Base Station has DHCP/NAT turned on. If so, instead set your AEBS to Bridge Mode (this will probably work on Airport Express too). This assumes you have a cable modem or other router/switch that you can use instead for DHCP/NAT. No more slow/stuttering video.
[crarko adds: I restart my Airport Extreme every few weeks just to flush the memory and have not experienced any trouble paying video. I do use it for DHCP/NAT on my network.
What I have noticed is that after prolonged use, my Apple TV (2nd generation) does have stuttering and will sometimes just lose it's connection to, say, Netflix. I have to reboot the Apple TV to clear that up, so I don't think it's an issue with the Airport.]

