Añado más información.
Aquí tenéis uno de los enlaces que comentaba. Este enlace lo tiene una web que me enlazó y que me traía bastantes visitas. Como podéis comprobar, tiene el formato antiguo (año/mes/dia/nombre_post):
http://compunoticias.com/2012/04/28/...l-de-internet/
Sin embargo, al tocar el enlace, ya veréis como, en vez de transformarse al nuevo formato, coge otro formato totalmente distinto.
http://compunoticias.com/agrega-a-tu...l-de-internet/
Como es natural, esta web no existe, y por lo tanto, aparece el error 404.
Mirad, os pongo el redirect que tengo en el .htaccess
RedirectMatch 301 ^/([0-9]{4})/([0-9]{2})/([0-9]{2})/(.*)$ http://compunoticias.com/$4
A ver si con estos datos podemos sacar algo más en claro...