I had a similar problem, and it was because I had hidden my SSID (that is a setting on the wireless router).
It seems that Ubuntu 9.04 does not like that.
Making your SSID visible does make your wireless less secure, I suppose brute force attacks are easier if people can see the name of the router. I changed mine to visible, as would rather have it working, than more secure and not working