On the wireless screen, where you can see a list of the networks - in the top left there should be a link to "Set up a wireless network for a home or small office". Do that, and just to be sure, manually assign the key... that should do the trick.
Windows is probably just flaking out, trying to connect even though it knows the network is secured, hah.