If I remember right, somewhere in the 2.6.3X kernel there was a bug that
prevented authentication with wpa_supplicant and WPA/WPA2 encryption. It
was also present with several motorola Android models when they pushed an
update. So if you get back to the factory settings on the router as Leslie
indicated, and it still doesn't work, updating the Ubuntu system could be a
possible solution if it is older or outdated.