La única solución que yo puedo darte es cambiar el router. Pronto tendrán que dar las compañías nuevos routers a los que, creo que es tu caso, no lo teneis compatible con el nuevo Protocolo de Internet (ipv5), pero no sé las fechas que ha puesto cada operador. Si se te ha acabado la oferta que dan las operadoras de bienvenida podía ser una buena solución lo que dices de cambiarte a otra, nuevo router y nueva oferta. Un router decente anda sobre 10-20 € en eBay, lo malo es que lo tendrás que configurar para tu operador. También puedes buscar uno que proceda de tu mismo operador, éste es de jazztel:
http://www.ebay.es/itm/ROUTER-ADSL2-...item2573a0bdc3, aunque yo no uso modelos tan recientes, la marca me sorprende por lo bien que se portan.
El tutorial habría que buscarlo para un modelo concreto. Si optas por comprar uno, intentaría echarte una mano con la configuración.