Solucionado!!
Lo arregle poco después de postear, el problema era simplemente "grabar/configurar" de nuevo los Ajustes de Conexión de Internet en la PS3(sin tocar nada), excepto el MTU lo tenía en Manual(teorías mias xD) y lo puse Automático como viene de seríe.
No he comprobado si era por grabar de nuevo la configuración de la conexión o por el MTU, quien quiera que lo compruebe y lo postee...
Ahora encuentra partidas al instante(máximo 20-30seg) y a todas horas, va genial.
No era ni el router, ni la conexión adsl , ni los puertos ni nada, sólo eso... lo último que se puede pasar por la cabeza cuando la PS3 funcionaba fenomenal con esa conexión y otros juegos online.
Espero que os ayude a los que os vaya mal.