it sounds like a problem on the server with saving session variables.
The Session ID should not change, it should stay the same.
use the attached session Test page to test the server configuration, if the test fails, it is probably the session.save_path setting in the php.ini file, you will need to contact the host to have them fix the problem.