Buenas Jrlk
Me temo que estás un poco confundido en varias cosillas.
En primer lugar, Movistar no bloquea ningún puerto de destino ni de origen. De echo lo único conocido que Movistar bloquea y que se requiere intervención por parte de ellos es el tráfico entrante DNS (que no el puerto 53), y solo si viene desde redes externas a Movistar, que se hace por seguridad, en cuyo caso hay que tener una IP fija y solicitar el desbloqueo. Quitando eso, no existe tal bloqueo, y como comprenderás, mucho menos para el puerto destino 25.
En segundo lugar, la prueba que realizas con traceroute creo que no entiendes bien que es lo que hace. El parámetro "p" especifica el inicio del rango de puerto de destino que se va a usar para enviar el paquete, que irá incrementando en 1 por cada salto, al mismo ritmo que el TTL, que es como funciona traceroute. Dicho de otro modo, el primer paquete se enviaría al puerto 25, el segundo al 26... y así sucesivamente. Lo cual no sirve absolutamente para nada para determinar si un puerto se bloquea o no se bloquea, ya que lo que pretende un tracert es dictaminar los saltos intermedios trampeando el valor TTL. Más aun, lanzado desde un equipo de la red local, al usar "-p 25" el paquete tracert enviado al puerto 25 sería al Router, puesto que es el primer salto, el siguiente salto se llevaría por el 26, el siguiente por el 27... al destino final, en el caso de que el tráfico fluyese correctamente, podría ser a lo mejor el 30, 35...
Respecto al intento de conexión de Telnet y respecto al resultado de tracert (con independencia del puerto que hayas especificado que como digo no vale absolutamente para nada), dicen claro cual es tu problema, y nada tiene que ver con puertos:
"network is unreachable"
Teniendo en cuenta que parece que alcanza la puerta de enlace del Router, y que lo haces desde linux, yo diría que el problema está en que te has equivocado de plano, y en dicho equipo has configurado una IP y/o puerta de enlace equivocada, con lo que el Router descarta tus paquetes, como es lógico y natural. Asegúrate que tanto la IP como la puerta de enlace y máscara de tu equipo es correcta.
Como digo, absolutamente nada que ver con puertos, bloqueos...
Saludos.