WordPress Posts Out Of Order after 3.1 Update

Simply add orderby to your query_posts

<?php query_posts($query_string . '&cat=-4&orderby=date&order=DESC'); ?>

Update

try:

global $wp_query;
$args = array_merge( $wp_query->query, array('cat' => -4,'orderby' => 'date','order' => 'ASC'));
query_posts( $args );

and if you still get the same change ASC to DESC.