I have never (FC3 or now F4 test2) managed to get NetworkManager to connect to a network using an encryption key. I have tried just entering it 'straight' and by using the 0x prefix that system-config-network uses. I am able to connect with system-config-network, but with NetworkManager it have never succeeded. If there are any logfiles etc. I can provide to help debug this let me know.
Christian - Have you tried using the passphrase instead of that actual key? That's what is supposed to go in.
Try having a terminal open with "tail -f /var/log/messages" while you attempt to connect to an encrypted network. It'll give you a lot more information about what NM is doing. I also had problem until i realised i had to use the "ASCII key" option for my encrypted airport extreme AP.
Ryan, there is no passphrase, our wifi router just lets us choose from a list of keys. Jeroen, I am going too attach a var/log/messages output to this bugzilla. As we are able to connect with system-config-network I assume our router don't need re-configuration.
Closing this bug as I noticed it was just me never realizing I could change the type of key to be entered. Seems my problem was exactly the same as Jeroen's. Should be message saying you need the 0x prefix though (or better, not need the 0x prefix)