It can be Verizon, but far more likely it is the web site on the other end.
The usual sequence of events is that when a large organization (like Verizon) enters the ISP market, they need a lot of IP addresses in a hurry. A classic example was when 'Home' collapsed about 5 years ago. It forced the part owners of HOME to directly enter the ISP business, and they suddenly needed a large number of IP addresses. Unfortuately they knew nothing of the history of these IP addresses.
They get the IP addresses allocated. The bind is that often a significant number of these IP addresses have, shall we say, an unsavory past. They were used in the past for denial of service, hacking, and other attacks when they were unallocated. The standard approach by the site owners is to black list those IP addresses. That means they are blocked through no fault of verizon.
A few years ago I had a situation where I had two accounts, one on my Cable provider, and one from the local phone company (US West), and I had a lot of trouble with sites that worked fine when I connected via dial up, but didn't work at all over the Cable connection. It turned out the IP address assigned to me by the Cable company (Thank you COX communications, who were exceptionally unhelpful) did indeed have an exceptionally unsavory past. I eventually contacted the technical contact at the site (via whois.com), and asked them to unblock the IP address, as it now was assigned to Cox Communications. They eventually did, but COX was to be polite, unhelpful.
(And that is one of the reasons I will never be a Cable Company Internet user again).
So to fix your problem, you are going to have to contact whoever the technical contact is at the blocked site, and ask them to unblock your IP address.
While in theory you don't have a static IP address as a residential FIOS customer, the reality is that unless the MAC address on your router changes, your IP address probably won't either, or at best it changes only on rare occaisons.
That has been my experience anyway.
What Mattheww says is very possible, but I think the problem might lie more in your security settings. Is this problem exihibiting on only one computer? The way your message is written, it sounds like this is the case.
If you are using IE as your browser, click TOOLS on the menu, then INTERNET OPTIONS, then SECURITY tab. Make sure all the zones are set to 'default level' and then apply the settings.
Next, click on the GENERAL tab, and click the 'delete' button. In the next window, click on the 'delete files, cookies, and history' buttons, and then select "apply".
Now, exit IE, and restart it. Try to visit the web sites you couldn't visit before.
If you are using another browser, the adjustments should be somewhat similar.
From my laptop I cant log on with my verizon router but can use the same laptop with a sprint aircard and I have no log-on issues, same browser. I also found if I use Firefox from our PC I have no issues either....
I had the same exact issue with other websites like youtube, disney, weather.com. After about two weeks of phone calls with verizon, they determined it was an ip routing issue and they resolved it on their end. Call their tech support and they should be able to fix as they know about the problem.