Thank you,
At least I know I'm not missing something really obvious... It really does appear to be that complicated :~
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.
Again, thank you for this suggestion! Can you or anyone else reading this recommend a good tutorial for splitting serial time interrupts? To be clear, I'm not asking anybody to write it for me, I just haven't had any luck searching for the right resources.
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.
I have to say... As happy as I was to finally see a branded GSM solution from Arduino, I really have to question its value when taking the price tag into consideration... Basically its only really useful for sending data from digital or analog inputs as long as the data isn't coming from the serial port and only if youre sending the data to another SIM card on the same network? Those are some pretty heavy limitations for a +$100 piece of equipment!
EDIT Found a promising tutorial at http://arduino.cc/en/Tutorial/TwoPortReceive. I will post results soon.