Seems like your cookies aren't getting picked up at all .. if it had anything to do with LoginTimeout, you should still see the cookie next to the first "ad_user_login:", and you should still have "untrusted_user_id" not zero.
My best guess it that your site is sitting on a subdomain or anotehr OpenACS install, for example if you have a site "foo.com", and another at "bar.foo.com", then some browsers will send cookies set for foo.com to bar.foo.com, and those cookies thus will not be valid.
If the problem still persists, I think the next step would be to verify that the cookies that get set are also the ones that the server gets back from the browser. Developer-support's request info page should be helpful here.
/Lars