If you keep getting a redirect on login error, try calling the upgrade page directly (yourdomain.com/wp-admin/upgrade.php). If that works, click the link, then try logging in again.
I figured this out upgrading a site from 1.3 to 1.5.1, where the secret salts are introduced. This worked for me, after trying everything else under the sun.
