Sounds as if you may be getting bit errors on the software serial connection. You may be able to reduce the frequency of the errors by playing with the serial parameters (you'd need to reconfigure the GPS to match, and I don't know what that would involve) or perhaps it could be affected by the properties of the circuit between the GPS and Arduino.
If you can't eliminate the errors, could you validate the received string to ensure it is syntactically correct before you store it? Evidently the string is only expected to contain decimal digits, a minus sign and whitespace so it should be easy enough to pick out the spurious characters.