I have the same problem.
1- The GSM I'm using is ARDUINO GSM SHIELD 2 (INTEGRATED ANTENNA)
2- The board is Arduino Mega
3- I follow the instructions in the link to connect the shield
a pic for the real circuit
4- I use SIM with no PIN (I remove the PIN) and there is a credit
5- I run the following code (the code of Sending a SMS message) with changing the number to my number
#include <GSM.h>
#define PINNUMBER ""
// initialize the library instance
GSM gsmAccess(true); // include a 'true' parameter for debug enabled
GSM_SMS sms;
// char array of the telephone number to send SMS
// change the number 1-212-555-1212 to a number
// you have access to
char remoteNumber[20]= "0535863840";
// char array of the message
char txtMsg[200]="Test";
void setup()
{
// initialize serial communications
Serial.begin(9600);
Serial.println("SMS Messages Sender");
// connection state
boolean notConnected = true;
// Start GSM shield
// If your SIM has PIN, pass it as a parameter of begin() in quotes
while(notConnected)
{
if(gsmAccess.begin(PINNUMBER)==GSM_READY)
notConnected = false;
else
{
Serial.println("Not connected");
delay(1000);
}
}
Serial.println("GSM initialized");
sendSMS();
}
void loop()
{
// nothing to see here
}
void sendSMS(){
Serial.print("Message to mobile number: ");
Serial.println(remoteNumber);
// sms text
Serial.println("SENDING");
Serial.println();
Serial.println("Message:");
Serial.println(txtMsg);
// send the message
sms.beginSMS(remoteNumber);
sms.print(txtMsg);
sms.endSMS();
Serial.println("\nCOMPLETE!\n");
}
5- the serial output is
6-from reading the solutions provide by members I update the GSM3ShieldV1AccessProvider so the serial output is
what is the problem why it gives me not connected! 
:o
