1. Have you only tried to get a signal from one location, can you actually go near a tower (like near an AT&T corporate store, they often have towers/repeaters at them)?
2. While powered ON, pull the battery, replace and reboot the BB.
3. Do you have a BlackBerry Data Plan from AT&T?