Haven't looked them over real hard, but one thing I don't see is a common ground between the Arduino and the GPS. I see that you are powering the Arduino from the USB port of the PC, but does everything share a ground?
Easy thing to try is connect a wire from the Arduino ground to the all the oter grounds. 2 devices being powered from seperate supplies need to share a ground for data. I have done that to my self a few times.
It don't look like your problem is that simple, but you never know.