New install - Administrator is not staying logged on long enough to do anything - immediately in logged off state

Just installed drupal 4.7 on a new vps. Copied the files, created the db and ran the sql file to create the db schema. Have done so similarly on about 6 other drupal installs.
This one appears to have gone through smoothly, however, after creating the first administrator, it takes you to a page to change the password. When you click on submit, it tells you that you need to login. So, I login using the original password drupal sets and it takes me back to the change password page. Doesn't let me change the password.

Appears that as soon as the login occurs, it reverts the user back to anonymous. I've never seen it do this with the other installs. This is a plain vanilla install. I'm following instructions to a T. The thing is this is a new server, but it's identical to another one I have, which hosts 5 other drupal installs.

Let me see if I can put this in chrono order:
1 -- I login from the root directory:
www.referralsuperstar.com
userid: admn
password: 87tPXchqoN

2 -- It shows me the root page with admin logged in.
3 -- I click on 'administer'
4 -- I get 'Access Denied' - You're not authorized to access this page.
5 -- A look at the logs (after logging in a few times) shows this:
user 12/08/2006 - 09:36 Session opened for admin. admin
access denied 12/08/2006 - 09:36 admin denied access. Anonymous view
access denied 12/08/2006 - 09:36 user/1 denied access. Anonymous view
user 12/08/2006 - 09:36 Session opened for admin. admin

I've tried a bunch of things including:
restarting mysql, rebooting the vps, restating http daemon, completely removing and re-installing drupal from scratch - once just the db, the other time with a brand new account in the same server - same behavior. I've verified by logging in as root and logging into mysql with the drupal db user that it has lock table privileges.

I would really appreciate any help you can provide. I can't do anything with this server - It's dead in the water.

Thanks.