It won't take five minutes to negotiate. The difference between simple WEP and WPA successfully negotiating is perceptible -- but only a matter of seconds. The problem can arise if you have a marginal signal at which point the delay or something seems to sometimes be relevant to non-connection.
I didn't say use WPA2 though the problem you mention may be to do with not supplying a password to the wireless adapter.
Try connecting without security. Then try connecting using WPA-PSK TKIP.