One tip - I find it useful to have the key on a USB stick, so I can copy and paste it rather than (mis)typing it!
Given that the connection works when no encryption is used, I wonder if the problem is to do with a mismatch between what the Wireless Access Point (WAP) is configured with, and what the EEE is set up for - e.g. WEP vs. WPA or WPA2.
To state the obvious, the client must have the correct settings for authentication type (WEP / WPA), the encryption type (AES or TKIP) and key provision (Open or Shared for WEP, WPA or WPA-PSK - pre-shared key - for WPA) to match the WAP settings.
Also a common problem is that some WAPs can be set up with a password that generates the WEP / WPA key, but you have to put the key into the client, not the password - if you see what I mean.
SD