Does it connect with other security settings?(security disabled or WEP) Is problem only WPA related?
Have known other network problems where implementation of WPA seems slightly different in some hardware. HAd problem with new Vista laptop and SpeedTouch router working with WPA that was only resolved by upgrading firmware of router. Win XP laptops all worked fine with older firmware.