A quick update on my progress:
I started by extending the wires by 30cm which brought only a small improvment. Moving GND from pin 2 to 20 improved it a little bit more. Soldering the wires directly to the battery leads improved it further. As I suspected the interference came across the wires, I ran the wires through a ferrite ring, which also helped.
All this was tested away from the case. When I put the unit back into the case, the fix was lost again.
As I received a second Primer last week, I switched over to that unit an - surprise! - the GPS works on short wires inside the case. Seems to be a problem with that specific Primer.
@Shadow: Pin 2 has only 2.8V, not enough to run the GPS.
Thanks for you help,
Klaus