I've got the same exact setup as Mike Whitt. Have had new AirPort Express working flawlessly since installing it two months ago. I have ATT Uverse Internet but have the wireless disabled on that box and have instead been using the Airport Express. For two months, absolutely perfect performance in my one-story house with 3 iPhones, 1 iPad, old MacBook, Wii, iMac, and several USB wireless adapters used on a PC desktop. All saw the network perfectly and worked without flaw using various 802.11g or n connections.
Then, last night, several things stopped connecting. My Windows 8 PC would see the network sometimes but not see it most of the time (even when in the same room). The most frustrating thing is that it does see the same 10 neighbors consistently, just not the AirPort Express that had been so consistent for two months. When my network did show up in the available networks list, it had 5 bars of signal and would connect but then immediately disconnect. By the way, plugging in the same PC using the AirPort Express Ethernet port works fine. Today I realized that my son's Nintendo Wii will no longer connect. It actually says it's connected, but then fails soon after.
I have be completely frustrated over the past two days. I'm quite experienced with network equipment and this seems to be a Wireless issue alone in my case. The network comes and goes from the available networks list even though it's in the same room as the connecting devices.
The really odd issue is that my new iMac, iPad, and iPhones are working fine and stable. Now that I think of it, it seems to be the 802.11g devices that are losing the connection. I'll need to look into that a bit as a possible channel issue with the numerous neighbors with wireless networks.
I'll keep reading this discussion in the hopes of finding a cause of such a strange change in reliability.