Are your apps themed or inverted? Any apps that have been tampered with will fail on an update from the market. The signature, from the developer of the app, is changed when you theme/invert it. So, when the signature doesn't match up, it will just fail and not update.
Funny how some people complain more than my 2 year old daughter does.