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
Serial.println("GSM networks while not Connected");
notConnected = false;