I am having what appears to be the same problem. I have tried two different SIM's, one being the Telefonica M2M which came with the Shield and the other another data SIM tested in another product.
Its a new Shield which I received today and I have tried several of the sample projects.
The gsmAccess.begin never returns and hangs, I am Monitoring the serial port, only once and last message received:
"GSM networks while not Connected" :~
// Default no SIM
// Start GSM shield
// If your SIM has PIN, pass it as a parameter of begin() in quotes
while(notConnected)
{
Serial.println("GSM networks while not Connected");
if(gsmAccess.begin(PINNUMBER)==GSM_READY)
notConnected = false;
else
{
Serial.println("Not connected");
delay(3000);
}