Connection Problems with GPRS Shield
It seems it can't register on the network, GSM modems are power hungry, are you sure you're powering it up with the external power source (through Vin)? Pretty sure the Arduino isn't enough, but I could be wrong, that's a shield that has those issues in mind.

Also try to see the signal strength using AT+CSQ.