Have you considered re-installing an older version of the firmware? Those updates seem to break as many things as they fix. My Linksys was giving me a devil of a time with media streaming to my Xbox360 and after I tried every troubleshooting tip I could find, a firmware downgrade did the trick. Haven't had a hiccup since. Just another thought.
I've heard lots of positive recommendations for Buffalo networking products in the past, but I don't know it its legal issues are behind it.
http://www.buffalotech.com/comparison-charts/wireless/