Are you using somthing (MAX232, etc) to convert rs232 levels and voltages to TTL between the GPS and the Arduino?
-j