WPA-PSK is already usable in WinXP and IRRC I already set up a WLAN with WPA-PSK and a Vista Client. Even without transmitting the SSID. Though that was troublesome...
Sorry, the problem has to be in your router (maybe yo're spreading mixed mode -> put that to only ONE mode -> Wireless G or N whatever your router is capable of)
OR
the prob is in your settings (we are humans we DO make mistakes
)
OR
the prob is in your WLAN-receiver (PCI / PCMCIA / USB - device) which maybe needs the latest driver for higher encryptions.