sounds like the host may have an issue with session management.
Try downloading the session test page from this post:
showpost.php?p=23826&postcount=2
to test the server session management, if this test fails, you will need to contact the host to have the session management issue resolved.