Recent versions of the IDE use SoftwareSerial. Why are you using NewSoftSerial?
Can you change the speed of your gps to something less fast, say 28800 or 14400? Arduino runs 16MHz crystal frequency so its 38400 is not exact when it uses its clock to time software serial inputs so lowering speed may help. If you're off by 10% then you get a wrong byte thus some special character.