I'm having exactly the same problem, using gsm_shield_2 + arduino uno, with a SIM card by Movistar.
Have you pressed the power button? you need to power the shield until the "status" and "net" leds blink... some people was missing this.... but din't work for me as well...
I tried the solution suggested on the forums of powering with external supply (looks like the shield needs >700ma), but i can just receive the "Not connected" message on the serial monitor.
I tried the SIM card on my phone and it works perfectly... so something strange is happening on the arduino side.
I have full coverage at home, so i don't think it's related with it... maybe should try with a different SIM card? any suggestions or people with the same problems?
thx!