GPS is actually fairly simple to interface. It's RS232 at a reasonably slow rate. It has a checksum to help you verify the data transferred correctly. The checksum algorithm is well known and code is available for it.
The TinyGPS library (written by the NSS author) does a tremendous amount of NMEA parsing for you. Google it.
So, to make this work you need to:
- get the GPS off pins 0 and 1, since those are already in use (or stop using hardware serial)
- go get TinyGPS, since you're having trouble parsing NMEA yourself
In addition, for anyone to really help you, you need to post a complete sketch and schematic.
-j