Bem, entretanto já resolvi o problema e penso que encontrei a explicação.
Contrariamente à maioria dos possuidores que usam o site
http://garmin.openstreetmap.nl/ para gerar os mapas, eu uso o
http://extract.bbbike.org/ pois permite escolher a área que se pretende através dum polígono, o que permite defenir melhor a zona e poupar também alguns MB.
Se dos 8 formatos suportados no site todos funcionavam, já não é assim, provavelmente devido a alguma das últimas atualizações do 520. Neste momento só 2 funcionam, o OSM ascii e o Onroad ascii. No site refere que "By default all generated Garmin maps from OpenStreetMap data will use the code-page unicode (utf-8). However, some older devices don't support Unicode and some new devices have a broken DRM firmware. In this special case please use the ASCII style, supported for "osm" and "onroad". Garmin SRTM extracts use always the ASCII character set." Ou seja, só estes formatos ascii funcionam, todos os outros (OSM, BBBike, Garmin Cycles, Garmin Leisure, Onroad e Openfietslite) se os tentarmos carregar aparece a mensagem "Não é possível desbloquear mapas".
O estranho é que o meu mapa anterior, antes de tentar trocar, é Garmin Leisure... e funciona! Vá se lá perceber isto...
Petrix, para confirmar esta minha teoria, que site estás a usar para gerar os mapas? Se estiveres a usar o
http://garmin.openstreetmap.nl/ lá se vai a minha teoria, mas pelo menos ficas com a solução