This is not a new problem. People have been reporting it all over the place for months. A MySQL upgrade does seem to be a fairly common factor among the reported cases.
Regardless, upgrading to the latest WordPress has always appeared to fix it. Something with older versions of WP and newer versions of MySQL causes some kind of weirdness there.
It may be because some older versions of WordPress (around 1.5, maybe) did not explicitly specify the post-ordering, and so an upgrade of MySQL (and a reload of the tables) changed the row order in the database. Newer versions of WordPress always specify order of posts when they make their select statements.
Alternatively, running a repair on your database might rebuild the indexes and correct the problem. But really, if you're running an older WordPress, then your blog is vulnerable to intrusion. Older versions almost all have known security flaws. Upgrading is highly recommended.
http://codex.wordpress.org/Upgrading_WordPress