I had this problem with my phone for almost half a year. I would get the "HTC Sense is not responding" message over and over again, and it would cause my phone to lag and be generally unusable. None of the solutions I could find on the internet worked, and I tried just about everything to fix it-- I restored my phone to factory settings multiple times, spent hours and hours on the phone with HTC's crummy customer service trying to diagnose the issue, had them replace the phone, and bought a larger SD card. Finally, when nothing else worked and the problem still kept rearing its ugly head, I took the phone to a local AT&T dealer and
had them replace the SIM card.
BINGO! Solution found!
If anyone ever has this issue,
skip all the fooling around that I initially went through. Back up your contects through a google account and
have an AT&T representative replace the SIM card. Voila! Your problem should be fixed.