the first place to start is to test the hosts session management functions.
sue the session test page from the following thread:
showpost.php?p=23826&postcount=2
if the session test does not pass, it is most likely a problem with the session.save_path setting in the php.ini file, you will need to contact the host to have them correct the problem.