From the arduino to the gps:
5V -> VIN
GND -> GND
D2 -> RX
D3 -> TX
Basically, pretty simple hookup. The GPS strings are correct, if you need the raw output from the unit as well, I can take it outside with a laptop and capture.
My working theory so far is that the GPS unit might be fine, but the micro-controller where the flash memory would be is not working.
Also, to rule out any problems with the UNO, I also tried a MEGA2560 board I have, with same results, and I was able to use the arduino with a 16x2 screen using those 2 pins successfully, so I'm 98% sure the arduino is OK.
Sorry for the huge picture! Any way to set picture sizes on a img link?