It appears that WordPress 3.1.3 has changed the name of the login cookie, and it is now wordpress_[UID]
This confuses wp_super_cache in wp-cache-phase1.php at line 318:
if ( preg_match( "/^wp-postpass|^wordpress_logged_in|^comment_author_/", $key ) ) {
which can easily be changed to:
if ( preg_match( "/^wp-postpass|^wordpress_|^comment_author_/", $key ) ) {
to fix the problem.