Debo cambiar el numero de telefono. ayuda por favor!!

Hola que tal estais?
Necesito ayuda urgente y es que no se que hacer y os pido consejo.
Hace dos dias me instalaron una linea telefonica, el unico proposito para tener esta linea era el adsl, como me interesa lo de la "no permanencia" de orange, ataque.
El operador me dice que no me puede tramitar el adsl porque ese numero pertenecio anteriormente a otra persona y ha dejado una deuda bastante grande a wanadoo, por lo tanto no puede seguir adelante a pesar que yo le explico que el numero es nuevo y bla bla bla. Este chico me sugiere que llame a telefonica y pida un cambio de numero de telefono para poder tramitar todo lo del adsl.
LLamo a telefonica, les cuento todo este rollo, me dicen que no tienen porque no hacerme lo del adsl porque piensan como yo, que el numero no debe, es la persona. (Tambien esta persona dejo deudas en telefonica), y me dicen que si quiero cambiar de numero que lo haga, pero que no deberia de ser asi.
que hago? por favor alguna sugerencia?
se que lo mas facil seria que cambiase de numero. cuanto cuesta?
alguien sabe si esto me traera mas problemas en el futuro puesto que ese numero de telefono tiene una gran deuda? no deberia ser asi, pero yo ya no se que pensar.
Muchas gracias y perdon por el toston.