Is the new computer a laptop or desktop? That could make certain troubleshooting a lot simpler.
First thing that would happen if you called into the FIOS call center is they would have you powercycle your computer(s) just to make sure it isn't some weird glitch/caching issue. After that, they would ask you to powercycle the BHR (router) that came with your FIOS installation (they can do it from their end, but they prefer the user do so). At this point, 90% of issues have been resolved.
If still not working properly, they would then have you pull the power adapter from the BHR and let it sit for 30 seconds just to make sure it isn't the router having a stuck setting that wasn't solved by a powercycle. This fixes another 2% of issues.
Now at 92% solved, if still not working, they would have you do a factory reset on the BHR. This varies from router to router, but usually involves using a pen or a paperclip to push a tiny little 'reset' switch recessed into a hole in the back of the router. This solves about another 5% of issues.
Now at 97% solved, the next thing to look at if still a speed issue and you not being where you should be provisioned at is looking at the NID. That's the box where the fiber goes in and out comes your MoCA and/or Ethernet connection to your BHR/STB's. While it is quite easy for the phone tech to powercycle the NID, it is more effective to completely cut power off to it and reset it yourself first (to eliminate it as an issue if you have to call in). This involves not only unplugging it from the wall, but unplugging the UPS battery inside the unit. Once done, wait about 1-2 minutes for all residual charge to leave. Hook back up power and battery again. This solves another 2% of issues such as the NID getting glitched settings.
Now at 99% solved, if you still have issues, it is time to call your FIOS tech support. At this point, you will have done about 95% of the tech support they would have walked you through, thus saving you and them time on the phone (trust me, it makes the Customer Service Rep very happy as it makes their stats look much better and saves their job when it comes time to cut jobs based on performance).
Anything at this point is either a firewall issue (which i assume you have tried turning off just to make sure it isn't interfering) or a network/provisioning issue that requires a support ticket sent on to a Tier 2 tech (which usually gets taken care of within the hour). Usually happens to be something like the card at the plant was set to the wrong settings or a fiber got cut in an area and people are being shunted to another fiber thus reduced capacity and they have to get a tech out to fix it. Things like that.
**edit**
It is also possible, though not near as likely, that a firmware update pushed out on the network by Verizon could have screwed with your BHR and them checking the firmware of your BHR from their end or doing a line test just to make sure there isn't a ground/short somewhere in the home Between the BHR and the NID can find about 0.5% of problems.