Buenas.
A mi hace unos años también me pasó y lo solucioné instalando el "firmware" modificado que borra mapas y música del RNS 510. A partir de ahí, sí que me pillaba los nuevos mapas. Creo recordar que esto me pasó un par de veces.
El "Firmware" para borrar el disco, me lo bajé hace unos años por internet. Si no lo encuentras, creo que lo tengo en el coche en un CD. Os podría enviar una ISO por si queréis probar esta solución y no lo véis por internet.
Saludos.