Take your phone to a free wifi McDowell's or StarBox and see if it connects.
I just got off the phone with Verizon. They had me enter the MAC address of the phone into "permit PCs listed below to access the wireless network" into my wireless settings on the router and it worked. It's damn peculiar that it worked for nearly a year without having to do that. Oh well, learn something new every day. The version of the phone I received had a 9.12 were as my old one had a 9.11 on the white under the battery, so I guess may have earned myself a slightly newer model for the trouble.
PS. I was almost ready to do what you suggested and then decided I'd call them first. I was really surprised that they would be able to help.
Thanks very much for your suggestions though.
Edited by trelleck, 03 February 2011 - 02:41 AM.