When connecting to the Airport from another device like a laptop does it tell you anything useful as to security settings etc? TKIP, AES etc etc?
I don't believe so. My wife has used the wireless in our house dozens of times without any problem. The Wii downstairs has no issues connecting to the Airport either, but with the digital photo frame and now the router, I've got a 50% success rate

I checked again, and when I set the NIC to automatically get its settings, and if I remove all security from both devices, everything works perfectly.
I just noticed that on the wireless settings page in the Airport configuration utility, right under the password it says "WPA2 clients can join this network using AES-CCMP." Might that CCMP, whatever it is, be important?