Having just returned again from England and Europe, where my Linux notebook worked flawlessly with all sorts of wireless hosts, here's my suggestion:

There are two forms for a wireless network key: hexadecimal pairs, versus ascii passphrase.

Perhaps your software is defaulting to the wrong format?

At our first B&B in Britain, the key offered to us was a short string of uppercase letters and numeric digits. It was *very* ambiguous as to whether this was intended as a hexadecimal key or a passphrase.

After much experimentation, it was determined to be a 40-bit WEP hexadecimal key -- though oddly our wireless software wouldn't accept it as such until I switched all of the uppercase letters into lowercase letters.

Cheers