Buenas, pues después de unas cuantas horas de búsqueda y no encontrar nada (podría ser que no lo busque con las palabras adecuadas...) Pues me pongo a ver si por casualidad alguien conoce la solución.
Resulta que por encima de los iconos de los accesos directos, se me ha puesto el icono de como si no encontrara el programa asociado, aunque los programas asociados funcionan correctamente.
He probado a eliminar el cache de los iconos, pero no hay manera, se me pone el icono por encima del normal, y de ahí no lo saco.
Saludos.