Ich habe heute exakt das gleiche Problem gehabt und bin durch Google auf dieses Forum gestoßen.
Ich hatte das Gerät (60csx, Firmware 4.00) vor ein paar Wochen ausgeschaltet, heute wieder angeschaltet und es wurden keinerlei Satelliten im künstlichem Orbit angezeigt. Und auch Gerätedatum und -zeit waren vollkommen falsch, statt 7. Oktober sollte es angeblich der 26. August sein. Es nützte weder Neuortung noch Masterreset.
Die Lösung: Ein Firmwareupdate mittels des Garmin Webupdaters. Dieser bot mir eine Softwareaktualisierung für den GPS Chip an und nach Installation hatte ich nach 2 Minuten Satsuche wieder prächtigen Empfang.
Ich habe mich dann gleich hier angemeldet, damit andere auch von dieser Lösung erfahren.