Besides tweaking the code to use AltSoftSerial, (which doesn't look particularly up-to-date), the only solution I can think of is to use a Mega/Mega ADK for its multiple hardware serial ports.
The easiest solution is to strictly split the time between the two serial interfaces. Use a higher baudrate (38400) to communicate with the GSM modem to make the periods with disabled interrupts as short as possible. Don't communicate with the GSM modem while you're communicating with the GPS, you even might clean the receiving buffer of the hardware serial after you finished the communication with the GSM modem.
The main reason I haven't bought a GSM Shield from Arduino is the decision of the Arduino team to use a software serial implementation for the communication with it.
Can you or anyone else reading this recommend a good tutorial for splitting serial time interrupts?
Have you had any luck with this yet? I seem to be in the same predicament.
I don't believe that that is what was suggested. Re-read what was suggested.
You can only control whether you are paying attention at the moment data arrives. Given that, it seems obvious that you don't want to not listen to either device for any extended period of time.