Why doesn’t wp_update_post() update the post_status field?

Answer couldn’t be simpler.

As pointed out by Otto at the wp-hackers list, problem was me not setting post_date_gmt when using wp_update_post().

Final code looks like this:

if ( $post_date < strtotime( "tomorrow" ) ) {
        $status="publish";    
        $newpostdata['post_status'] = $status;
        $newpostdata['post_date'] = date( 'Y-m-d H:i:s',  $post_date );

        // Also pass 'post_date_gmt' so that WP plays nice with dates
        $newpostdata['post_date_gmt'] = gmdate( 'Y-m-d H:i:s', $post_date );

    } elseif ( $post_date > strtotime( 'today' ) ) {
        $status="future";    
        $newpostdata['post_status'] = $status;
        $newpostdata['post_date'] = date( 'Y-m-d H:i:s', $post_date );

        // Also pass 'post_date_gmt' so that WP plays nice with dates
        $newpostdata['post_date_gmt'] = gmdate( 'Y-m-d H:i:s', $post_date );
    }

    if ('insert' == $operation) {
        $err = wp_insert_post($newpostdata, true);
    } elseif ('edit' == $operation) {
        $newpostdata['ID'] = $post_id;
        $err = wp_update_post($newpostdata);
    }