first thing to double check is that the server is properly configured to save sessions.
use the sessionTet.php file from the following thread to test the server:
showpost.php?p=23826&postcount=2
if the test fails, it is most likely the session.save_path setting in the php.ini file, you will need to contact the host to have them fix the issue.
If the test passes and you are still having a problem.
try adding the following code to the login page after the <body> to double check what sessions are being set by login:
<?php var_dump($_SESSION); ?>
And look in the access rules manager to see how the Logged in to admin rule is defined.