Trouble with Parallex GPS and Arduino Mega2560

You can't use SoftwareSerial on pins 0 and 1 when you are using those for hardware Serial. Try pins 2 and 3.