Für den Fall, dass noch jemand diesen Thread liest und sich für die Lösung meines Problems interessiert (GPS Fix dauert zu lange):
Mittlerweile war der PNA bei Medion in Reparatur, wurde jedoch ohne Befund zurückgeschickt. 
Nach weiterem Testen hatte ich den Eindruck, dass wahrscheinlich ein Wackelkontakt vorliegt, da das Gerät oft den Empfang verloren hat, wenn ich es in die Hand nahm bzw. bewegte.
Darauf habe ich es aufgeschraubt und vorsichtig an der Platine gebogen und die interne GPS Antenne bewegt. Ganz deutlich hat das Gerät dann oft innerhalb ca. 1 Sekunde den Empfang verloren und wiedergefunden. Der Empfang war dann immer sofort wieder sehr gut (HDOP < 2 und über 6 Satelliten).
Gesehen habe ich leider keinen Wackelkontakt. Da ich die GPS Antenne in Verdacht hatte, habe ich sie abgeschraubt und den anderen Kontakt abgelötet. Danach habe ich sie wieder neu befestigt/angelötet.
Siehe da, das Gerät funktioniert jetzt ohne Probleme. Der GPS Fix ist innerhalb kürzester Zeit vorhanden.
Ich fürchte allerdings, dass es vielleicht nicht an den Antennen-Kontakten lag (die sahen nämlich gut aus), sondern dass ich zufällig irgendwo angekommen bin und so zur Zeit alles funktioniert. 
Schwach finde ich, dass Medion den Fehler nicht gefunden hat. Immerhin trat er fast durchgehend auf.
Ich frage mich, da die Medion Arbeiter wohl nicht unter freiem Himmel arbeiten, ob eine externe GPS Antenne zum Testen verwendet wird. Dann könnten sie natürlich keine Probleme der internen Antenne finden.
Ein Freund von mir hat das gleiche Gerät und hin- und wieder ähnliche Probleme. Gibt es noch andere mit dem Problem? Vielleicht ist eine ganze Serie mit Fehler gebaut worden?