Here's what happened: I moved the morning of April 20th, as scheduled, and the aforementioned modem was sent to me the same afternoon. I hooked everything up that night at 8pm as ordered, but only the phone service worked. The tech support did their best to trouble shoot over the phone and even sent out techs to work on the phone lines of my apartment building but nothing came of it.
Last week, I sent the first modem back and canceled service, but changed my mind last Saturday, after speaking to someone in customer support, who suggested that the modem I returned may have been to blame. They sent me a new one, the Motorolla NVG510 -- a wireless gateway/modem. I received it yesterday afternoon and hooked it up, save the ethernet cord to my computer (because I still needed to be able to use dialup) and noticed that all the lights that would have been on -- power, broadband and service -- if uverse were functioning, were in fact on. So I plugged the ethernet cord into my computer and rebooted the system. Uverse was working, one day earlier than promised, so I registered and skipped the toolbox download (that only works for Windows anyway) and I was online with high speed again, after nearly a month without.
I am very happy that I spoke to AT&T's customer service. When I think of all the time I spent worrying that the service or modem would not work
with my computer and the only problem was a faulty modem. Installation was quick and easy. I don't think uverse is faster at the same speed as dsl, but it works just as well for me... so far. And with Debian there was no compatibility issue whatsoever.
I just hope they honor their promises of no service activation fee and $100 rebate for the $100 gateway they sent. With AT&T you never know.