Ironically I had much of the same problems when I moved from San Francisco to New York in 2001, and for about a month or so was without Broadband because the companies could not figure out what was wrong.

bq. When I moved to my current house last year, I tried to sign up for DSL high-speed Internet service. However, Verizon’s Web-based
qualification form told me I was too far from the central office.
So I went with a cable modem. I’ve noticed construction work at
our local central office the past few months, so a few weeks ago I
thought I’d check again to see if they upgraded the facilities to
extend DSL coverage. Both Verizon and Earthlink indicated I was
now qualified for DSL. Oh happy day. [Werblog]

Well read on for Kevin’s trials and tribulations.