UIDs on System Inconsistent

[CFalcon]

On my EVO 4G, there's an error saying "UIDs on the system are inconsistent, you need to wipe your data partition or your device will be unstable. It also had a button that says "I'm feeling lucky". Now my settings are half missing, my address book is gone, my browser doesn't work and all the apps on my sd card are gone.
What can I do about this? Do I really have to factory reset my phone?

I had recently purchased a new battery, if that has something to do with it. Everything had been running fine until I restarted the phone using the power button. And I've gone trough a couple resets with the new battery with no problem.

And just to be clear, I'm not using any modifications or anything. It's a boring, stock EVO.

 

[KENNECTED]

On my EVO 4G, there's an error saying "UIDs on the system are inconsistent, you need to wipe your data partition or your device will be unstable. It also had a button that says "I'm feeling lucky". Now my settings are half missing, my address book is gone, my browser doesn't work and all the apps on my sd card are gone.
What can I do about this? Do I really have to factory reset my phone?

I had recently purchased a new battery, if that has something to do with it. Everything had been running fine until I restarted the phone using the power button. And I've gone trough a couple resets with the new battery with no problem.

And just to be clear, I'm not using any modifications or anything. It's a boring, stock EVO.

• What apps have you recently put on your device?
• Is you contact list/address book, calendar & tasks there when you check on a desktop? Hopefully you're saving to your google account and not the phone.

The battery should have nothing to do with this.

 

[CFalcon]

Um, It seems I have all my numbers saved to my google account... I recently installed Sketchbook and some mad lib apps. They seemed to work fine before though.