US Telco Support > Verizon > Verizon Online DSL > [speed/latency] lower dsl sync and speed after Sandy

Verizon Direct here on this website may also be able to help, but the last I recall they've been playing the "Automatic speed for package" game and they also don't have access to the billing records.

If memory recalls, if you were to dial just the standard 1-800-VERIZON number and then press the option for High Speed Internet > Technical support (they change the menus constantly), the agent you get on the line should have the ability to put in a re-provision request if they see the speed is off. Just explain your case saying the line after the storm has decreased in speed, you've tried rebooting your modem (which I assume has been done) and you'd like them to check your line profile. Failing that, someone in Billing would need to verify what package you have and then push for a re-provision if they see you're off (without adjusting your price/package, though).