Wie Glacier schon sagte:
In den meisten Fällen ist Datenmüll = falsche Baudrate

Überprüfe diese doch mal (soll heißen: Einstellungen des ATMega und die erforderliche Baudrate wie sie im Datenblatt des GPS-Modul angegeben ist)

mfg
LemonSquash