I had exactly the same situation as iBunny.
I got it working by changing the settings via Airport Utility from "WPA2 Personal" into "WPA/WPA2 Personal" and it worked. Btw, before this, I changed from channel 11 to 1, 1 to 2, 2 to 7 without success. I've kept it under channel 7 and just made the change mentioned above.
Also, under winXP, I went to Wireless Network Connection properties and filled up the preferred networks. Am not sure if this has anything to do with the problem at hand but I am now connected automatically.
Hope this helps.