Inconsistent UIDS and wiping a data partition
I found another solution:

Have a look at /data/system/uiderrors.txt. There you will find the apps that are responsible for the trouble. You can delete them (manualy if necessary) to fix the issue. Reinstalling the apps brings the error back, though.