I have an airport extreme in my home with my iMac running Leopard and a MBP running tiger. Both connect to it just fine. The one thing I do notice with the MBP, but it's probably more related to tiger than to the hardware is that for some reason it doesn't seem to remember the Airport network because I have it set to not broadcast the SSID. My iMac seems to deal with that just fine and remembers it.
I'm running WPA2 personal as you are. If you're not on the latest version of Leopard, I'd suggest upgrading first to see if that makes any difference. In the advanced area of the Network preferences, make sure you have the check box checked to remember any network that it's joined already.
When you enter in the network name and the WPA2 key, does it even attempt to connect or acknowledge the airport? If your version of Leopard doesn't have a check box to check for remembering preferred networks, upgrading might fix that or if you are not broadcasting the SSID (network name) from the airports, try doing so and see if it makes a difference.
