I have tried that and that's why I eliminated HW serial output to see if this is causing issue. Data is corrupting once in 3-10 second.
Receiving $@PGSA,A,1,,,,,,,,,,,,,,,*1E instead of $GPGSA,A,1,,,,,,,,,,,,,,,1E
Receiving $@PRMC,073405.491,V,,,,,0.00,0.00,111112,,,N47 insted of $GPRMC...
Strage, that only G character gets overwrited with @.
Also, does your program work with slower update rates, like 4 Hz or 1 Hz ?
Another question would be if TinyGPS is capable of 5 Hz operation on 8 bit AVR? It does a lot of float and 32 bit long math. Can you try driving a pin high right before the call to TinyGPS stuff and low right after, like this:
digitalWrite(2, HIGH);
gps.stats(&chars, &sentences, &failed);
boolean result = gps.encode(c);
digitalWrite(2, LOW);
Just measure pin 2 with a multimeter. If you have a duty cycle measurement, use it. Otherwise, just look at the approximate average voltage. If it's tiny, then not much CPU time is being spent inside TinyGPS. But it it's something like 3 volts, then the number crunching might be too much for AVR-based Arduino.
I've measured with multimeter. Frequency is about 3Khz, duty cycle is 4.5%. Not sure if this is fine.