ARDUINO + GPS, SIMBOLOS RAROS

No dije eso. Sigues viendo las cosas como 3.3V y 5V y no como la corriente que necesitan.
Tu problema esta en los baudios o velocidad de comunicación. Prueba por ahi.
Luego vemos este tema.