that make me think the server is not setting session variables properly.
use the session test page from the following thread to test the servers session management:
showpost.php?p=23826&postcount=2
if the session test fails, you will need to contact the host to have them correct the problem, it is most likely a bad setting for the session.save_path in the php.ini