I had an issue with Ubuntu 12.04 with the latest updates (as of a couple weeks ago) not being able to connect to my router which is secured with WPA. It connected find to the unsecured guest wifi on the same router and to the secured SSID from under Windows on the same machine (an Acer Aspire One 756).
I assumed it was a recent update but when I booted from the Xubuntu 12.04 CD it had the same problem.
I'm guessing there's something odd on my router that is giving Ubuntu problems. I don't see any of the "improve media traffic" settings which gave me problems on my old Droid with some networks.
Any ideas on what to look for or how to fix it?