I would suggest starting by performing a battery pull - while the device is on, remove the battery for 15-30 seconds, reinsert and wait for the device to reboot.. The next step is to call AT&T to ensure that everything is set up and working correctly on their end. If it is, the next step would be to do the following:
Go to Options > Device > Advanced System Settings > Host Routing Table, press the BB Menu button and select Register Now. Your device should be sent a message from BlackBerry stating that your device is connected to the BlackBerry network.
If you get the message described in the previous step, go to Settings > Email Accounts, press the BB Menu button and select Service Books, then resend your service books.
If that still doesn't help or if you don't get a registration message, you may need to reload the software on your device. To do this, follow the instruction in the following link: