I'm experiencing a similar problem described in many posts that seems related to session handling.
I'm using PHP 5.0.4.
User log in... but it get the access denied page.
That happens randomly... sometimes they can login, sometimes they can't.
The problem seems related to the client setup... since I can't reproduce the problem here... but still... they are experiencing this problem just with drupal on that hosting.
They are using IE7. I've tested with IE7 and never experienced the same problem.
A first step would be to identify what's different in their setup that make them experience this problem... a second step would be to make the website work independently of their setup.
It doesn't seems to be the problem described here: http://drupal.org/node/139464#comment-254334
since they don't have multiple cookies nor they get the wrong password message.
I'm going to see if this get fixed pressing the magic "Reset" button in IE and see if they experience the same problem on other drupal sites or on any other web sites... but does anyone has any clue about similar situations?
It really does look as a client setup problem. But still...
thanks