I've also encountered this issue, and I assumed it was a bug to do with the fact that I sometimes use apt-get and sometimes accept the Ubuntu GUI software update prompts.

If people are encountering it on this wide a scale, it must be a truly severe problem (that's also probably causing many people who haven't learned about apt-get to give up on software updates entirely!).