Connecting to GSM/GPRS unstable, eventually hangs

Aaah, the infamous AT%13%

no reply and hanging. Lets see if Connecting problems with Arduino GSM Shield - Arduino GSM Shield - Arduino Forum gets something resembling that.

I have the same kind of problem.