Take the phone to your AT&T store and ask where the nearest Device Support Center is. They can re-update the phone, which is probably the problem. (Whatever it is, though, they'll figure it out. That's why you pay more for AT&T - great service.)
Make sure anything you don't want to lose is backed up on your computer - they may just give you another phone.