I work for an ISP that provides DSL service through Verizon, so I deal with them a lot. Here's the answers to some questions I've seen in this thread:
1. If your line supposedly only qualifies for 768/128 but you are reasonably close to the CO, then you might want to ask the tech if he can look into line conditioning for your line. This involves their removing devices in your area that would interfere with tihe DSL, keeping your service level down. They usually do this at no charge.
2. To the person who could not upgrade because the frame relay is only 768kbps, I'm surprised. The frame relay that they are talking about is the connection between Verizon Online's location in your city and the Verizon phone network. Your DSL connection goes from your home to the CO, then onto Verizon's phone network. To get to the Internet, it must go through your ISP's (in your case, Verizon Online is your ISP; they are a separate company from Verizon the phone people) connection to the Verizon network in order to eventually get out on the Internet. There are two types of connections that your ISP can have: frame relay and ATM. Frame relay is being phased out right now, and Verizon is moving toward ATM connections in all of their new locations. Frame relay connections top out at around T1 speeds I believe, while ATM can go up to DS3 and beyond. The problem keeping you from upgrading is that VOL's connection to the phone network is only 768kbps in your city, which means that all DSL customers are feeding off of that line. Nice, huh?

If the speed is not oversold, you don't really ever notice a difference between frame relay and ATM service. Frame relay service uses the good old Fujitsu dark gray modems usually, while ATM service can use a number of them, the most popular being Westell Wirespeed ones.
3. "Fire up the modem and let it sync" is one of Verizon's classic phrases. This is not something you should have to do very often. When you turn on the modem, its lights will blink for 30-60 seconds. This is called letting the modem "sync up" to the line. Once the lights are on steady, your connection is good to go. The DSL still is an always-on connection because this is only done when the modem is first powered on. I know that the older Fujitsu modems do require periodic resets of the modem for whatever reason; the connection will just go out completely until you power off and on the modem. If you call Verizon's DSL technical support center, the first message that plays asks you to reset your modem and reboot your computer first.
I think I can answer your questions pretty well on this topic, so if anyone else has any questions, I will do my best to answer them.