Many people have had problems with their posts suddenly appearing in reverse order. These mostly happen with older versions of WordPress, but even the latest version can display this issue with some themes and/or plugins. Sidebar lists of posts can suddenly show the first posts made on the blog instead of the most recent.
This problem is caused by a bug in MySQL version 5.0.51 (potentially other versions as well). Unfortunately, many hosting providers have recently decided to upgrade their database systems and chose this version. Newer versions of MySQL have fixed this bug.
For people running older versions of WordPress, upgrade to the latest version. Newer versions are not as susceptible to this issue, however certain edge cases will still exhibit the problem.
For people running the latest version of WordPress, talk to your host and convince them to upgrade MySQL to a newer version. Again, this is a bug in the version of MySQL they are using, it is not a WordPress specific problem, and it will likely not be "fixed" by WordPress. WordPress is doing the right thing, that bug in MySQL is causing the bad ordering.
If you need to convince them that it's a MySQL problem, tell them to come here. Or just tell them to read this webpage, which details the problem in MySQL: