Trouble with Parallex GPS and Arduino Mega2560

Maybe tell us which Parallax GPS you're using?

Is the convention with Software Serial that different from using the UART?
I successfully wrote a programme recently to read a GPS and store the results in an array.
I think that you have to check for Serial.available each time?
id est:

  while (serial_idx < 13)  // loop - capture hhmmss bytes
                           // GPSchar[07]..[12]
  {
    if(Serial.available() > 0)   //  ! ! !
    {
      GPSchar[serial_idx] = Serial.read();
      serial_idx++;
    }
  }