I had the same problem and the solution was very simple.
I used an external powersupply for the GSM-Module, and powerd the Arduino by usb. The problem was that i had no common GND. I just connectet the GND pin from the GSM-Modul to the GND from Arduino and it works.