Try using the same SIM card on another phone and see if it connects. If it works you probably need to reset, if not reflash, your phone. If not, it's ATT's fault, probably your account is not set up correctly.

What firmware are you using? Go to "setting->about product," and you will see the version information.

I always need to try 2-3 times before my n900 can establish a connection with ATT from a fresh boot. This occurs on both 2009.42 and 2009.51.