GSM Shield Not Connecting

Hello,

I went through several posts on GSM shield on the forum but could not find a solution to my problem.

I just bought a new GSM shield that I connected to an Arduino Uno and have been following these instructions

I tried with the Telefonica SIM as well as a SIM that I had from T-Mobile but could not get my shield to connect.

I ran the modem test code here http://arduino.cc/en/Tutorial/GSMToolsTestGPRS and it worked just fine.
Here is the code I am using

// import the GSM library
#include <GSM.h>

// PIN Number
#define PINNUMBER "1234"

// initialize the library instance
GSM gsmAccess(true);     // include a 'true' parameter for debug enabled
GSMScanner scannerNetworks;
GSMModem modemTest;

// Save data variables
String IMEI = "*MY_IMEI*";

// serial monitor result messages
String errortext = "ERROR";

void setup()
{
  // initialize serial communications
  Serial.begin(9600);
  Serial.println("GSM networks scanner");

  scannerNetworks.begin();
Serial.println("scannerNetworks.begin();");

  // connection state
  boolean notConnected = true;

  // Start GSM shield
  // If your SIM has PIN, pass it as a parameter of begin() in quotes
  while(notConnected)
  {
Serial.println("while loop entered");
    if(gsmAccess.begin(PINNUMBER)==GSM_READY)
{
  Serial.println("gsmaccess.begin");
      notConnected = false;
}
    else
    {
      Serial.println("Not connected");
      delay(1000);
    }
  }

  // get modem parameters
  // IMEI, modem unique identifier
  Serial.print("Modem IMEI: ");
  IMEI = modemTest.getIMEI();
  IMEI.replace("\n","");
  if(IMEI != NULL)
    Serial.println(IMEI);

  // currently connected carrier
  Serial.print("Current carrier: ");
  Serial.println(scannerNetworks.getCurrentCarrier());

  // returns strength and ber
  // signal strength in 0-31 scale. 31 means power > 51dBm
  // BER is the Bit Error Rate. 0-7 scale. 99=not detectable
  Serial.print("Signal Strength: ");
  Serial.print(scannerNetworks.getSignalStrength());
  Serial.println(" [0-31]");
}

void loop()
{
  // scan for existing networks, displays a list of networks
  Serial.println("Scanning available networks. May take some seconds.");

  Serial.println(scannerNetworks.readNetworks());

    // currently connected carrier
  Serial.print("Current carrier: ");
  Serial.println(scannerNetworks.getCurrentCarrier());

  // returns strength and ber
  // signal strength in 0-31 scale. 31 means power > 51dBm
  // BER is the Bit Error Rate. 0-7 scale. 99=not detectable
  Serial.print("Signal Strength: ");
  Serial.print(scannerNetworks.getSignalStrength());
  Serial.println(" [0-31]");

}

I keep getting not connected on my serial output. This is the first thing I tried to do with the shield out of the box and did not expect it to hit a roadblock so soon with all the documentation available.