mine is RS232 version, it use LS4000 gps detector. It work on my pda, maybe there is some problem with the protocol..
More likely, it is a problem with voltage levels. RS232 is +/- 12V. The Arduino is TTL (0/5V) which is also inverted. You possibly need a MAX232 chip in between.