GPS returns "yyy.."

You're lucky you haven't killed it. Dataasheet says:

Input voltage on any input connection +3.6V

TX on the arduino is 5V.

-j