Andy,
Are you running a cache for variables? I had a similar issue which was due to have APC enabled in the config but disabled in the php config. Wouldn't let me login until either I enabled it in PHP or disabled it in library/config.php as the session was not being stored anywhere.
Could be something similar for you?