For close to a year after my FIOS internet installation, I had continual problems with my wireless internet connection. It would work for a day and then not work again. I did boosters, new computer parts, many phonecall and visits by Verizon technicians and outside (paid) consultants, and even got a new (desktop) computer. Finally, the problem was solved VERY SIMPLY, following a suggestion by a Verizon phone technician -- REMOVE EXPLORER FROM THE START-UP TRAY OF THE COMPUTER. (The start-up tray determines what program options come up automatically when you log on.) Apparently there is some incompatibility between Explorer and the FIOS connection. It takes one stroke to revise the start-up tray, and I have had not one minute of trouble since then.
Thought I would share this information to save others the endless time and annoyance I spent trying to figure this out.
One of the problems you can have with MS windows(specially with wireless connections) is if windows starts and does not find a IP address from a dhcp server it will just not start tcp/ip services. When something like IE is in the startup menu it can start before the wireless connection is complete and you have received an ip from your router(dhcp server). You can bypass this by removing IE like you said but make sure nothing else in startup uses the internet. The other thing you can do is setup static ip for your lan on your router this way your computer always know what ip it has and you won't have a problem on start up.
Glad you found a solution. Just some advice for other who might run into the same problems.