GSM Shield Problem AT%13%Not connected

Have you followed the instructions here? http://arduino.cc/en/Guide/GSMShieldLeonardoMega