Need to see the code (use the # icon!) and some sample output.
and some sample output.
The only other thing that might be happening is that the data is inverted. Fortunately, the NewSoftSerial class can un-invert the data for you, if you set the (optional) 3rd argument to true.
It could also be the GPS is in binary output mode instead of NMEA ouput.