I recently replaced my wireless router from Verizon. I kept all the settings identical, and all the other wireless devices in my home connect with no problem (a pc, mac, ipad, etc). However, my iphone is unable to connect. It correctly identifies the wifi network, and I'm prompted to enter my password. But even though I've entered the password correctly multiple times, it always returns "password incorrect".
You could try this:
Go to Settings -> common -> reset (at the bottom). On the next screen you can choose which settings you wish to reset. Choose "Network settings".
I assume the stored settings are deleted now, and after a re-connect the connection should work.