Auto-connect to WPA2 protected 11g network after sleep or reboot?

I have recently switched to WPA2 encryption on my Airport Express (11b/g version) network from WEP. Everything works for the most part, but my iMac does not auto-connect after waking from sleep or reboot any more. I have to manually select the network from the airport menu bar. I did not have this problem when it had WEP. I am running 10.4.11 on an intel iMac CD. Any ideas?

BTW, I have checked my System Preferences -> Network -> Airport item and my network is the only one listed in my Preferred list and it is set to connect by default and if it cannot find any of the networks it is supposed to keep trying to find it. (I had it set to join an open one, but the problem did not get solved after changing this setting.) I have also deleted com.apple.networkconfig.plist, toggled the settings on the airport and tried adding the WPA2 password to my keychain, so far no improvement...

 

Well, mine was not in the keychain when the problems started and I believe I have removed my network from the preferred networks list and added it back again although I am not absolutely sure, maybe I should try it again. Is that what you changed in network preferences?

By the way, my location is "Automatic".