I don't know about the external power. Have you tried the GSM shield without the ethernet shield connected?
I do know that most usb ports will provide a maximum of 500ma.
I don't know about using the Mega setting. That sounds like a bad idea to me. Maybe you are running out of SRAM in the Uno?