I was having similar problems and spoke to Linksys support.

I had created a 4 character passphrase for the WEP encryption. The agent suggested I enter the full key code.

This worked for the 2 computers I was having this issue with. One Vista and 1 XP Pro.

Only the computer Gods know why - I hope this helps someone else out this aggravating situation.