SoftwareSerial was also a cause for consternation in my project as well as it Will drop or mangle a character once in a while. When I switched to a Mega most problems went away. Is it possible that you have RX connected to RX and TX connected to...? That will also give you the results you report. GPS_RX must connect to Mega_TX and GPS_TX must connect to Mega_RX. Where Mega_RX is serial1,2,3 same for TX.
There is a serial0 but that is also the data connection to the usb converter and as such restricted to talking to the serial monitor or programming via the bootloader.
If you need it I can modify the two or three places where serial is mentioned in the sketch I did and enclosed it. It's untested both my Mega's are busy but the changes are just to assign serial data to a specific hardware port instead of an object.
One last thing, Verify both GPS connections and speed. The Ucenter thing comes with instructions, You can get them from the U-Blox webpage.
Doc