I had this very issue and tried everything including removing from BES and readding. Ultimately I was forward from AT&T to RIM support and then to advanced support. We first removed a suspect Facebook application but that didn't do it so they removed my PIN and created a new one. After a reboot I was back in business.
Of course that is only a small problem next to all the others i'm experiencing.
but hopefully the warranty replacement will address the issue.