Puede ser que sea por ahi, pero he probado todas las configuraciones possibles, desde 9600, hasta 300, hasta 1000000 (o el valor màximo que sea).
Segun el datasheet del gps està configurado en 9600.
Segun parece en algunos foros en ingles, parece ser que el arduino UNO, (alguna de sus versiones), con segun que GPS, dan errores de este tipo, tendre que revisar-los mas a fondo, o cambiar directamente a una placa tipo MEGA.