Multisite Login problem

This is the relevant code from ms_site_check():

$blog = get_blog_details();

// truncated

if ( '1' == $blog->deleted ) {
    if ( file_exists( WP_CONTENT_DIR . '/blog-deleted.php' ) )
        return WP_CONTENT_DIR . '/blog-deleted.php';
    else
        wp_die( __( 'This user has elected to delete their account and the content is no longer available.' ), '', array( 'response' => 410 ) );
}

So while site might not be actually deleted, for some reason WordPress is pretty confident that it is. The first thing I’d look at are DB queries being generated/run and data which is returned.