I just had a productive chat with a Netflix customer care representative, who was in constant contact with his tech department during our chat.
It was pretty much mentioned on this thread already, but I'll say it again - stop messing with your Apple TV's, stop rolling back software, stop messing with DNS servers - it won't change anything.
I wouldn't say my conversation with this rep was an official statement from Netflix, but this is what he pretty much said at the end:
Netflix's recent changes behind the scenes (the nationwide SuperHD rollout - among other things) are most likely causing these recent problems with the Netflix app on Apple TV (and it won't matter which software version you are on.)
We tested setting the playback settings online in my netflix.com account to "medium" (which doesn't allow an HD stream) and with those settings my Apple TV would at least stream at 640x480 (1050 kbps). Before, when playback speed in my account was set to "HD", I was constantly downgraded to 320x240 (235 kbps). Needless to say - all my other devices stream Netflix at the highest possible quality for each device (720p for Macs and 720p for iPhones and iPads). - After that test the tech department concluded that it should not be too hard for them to fix this issue behind the scenes. I can hardly believe I was the first one to have them do that test - so take their comment with a grain of salt.
What the Netflix rep did say repeatedly was this - this problem will be fixed soon.
I reminded him that Apple sold 13 million Apple TVs, while Roku only sold 5 million units and he assured me that they were well aware of that.
So there you have it. All we can do at this point is wait. It also won't hurt to keep calling Netflix customer support. The more they hear from users, the faster it might move up their priority list.