Reviso todo en el plan, nombre de usuario, nombre de la carpeta, permisos NTFS, logs, cuenta del servicio SQL Server Agent, todo lo que se les pueda ocurrir.
Cuando ya daba todo por perdido, me percato de algo que me llamo la atención, la opción de la extensión de los archivos de backup en el Maintenance Plan estaba con ".bak" cuando se debería haber puesto solo "bak".
Una vez modificada esta opción, verifico como comenzó a correr correctamente, y el job a hacer lo que se suponia que tenia que hacer, borrar los backups con mas de 1 semana.
Hemos dejado a un usuario contento y le hemos resuelto su problema.