PostCode
Major contributor!
Ok. I just got back from a customers house. After spending the better part of an hour on the phone with some guy in India, most of which was me telling him to repeat himself because I couldn't understand a word he said, it turns out that the issue was the router. I had to apply a firmware update to the router in order for the PPPoE connection to authenticate properly with Verizon's server. The router that Verizon is sending with their modem is a Linksys Wireless G router. I have no idea is the exact same model/firmware is being sent to all customers, but if you live in an area that has been recently deregulated and you get Verizon Online DSL and experience this issue then check for the latest firmware update for the router.