I always hated OWA! I have seen this problem myself, and heard of it often.
Unfortunately, I don't know of the specific fix for it. It could be several things.
First off, Technet article 311422 states that, "In earlier versions of Microsoft Outlook Web Access (OWA), users must have the "Log on locally" right to gain access to OWA. In the Exchange 2000 version of OWA and later, this right is no longer required. The only right that users must have is the "Access this computer from the network" right, which is given to the Users group by default in Microsoft Windows 2000."
So, make sure that your domain users in your AD domain have the "access this computer from the network" right. I would NOT remove the "log on locally" right you gavethem, just to be safe!
Now, another Technet article I read (I didn't save the article #, sorry) stated to use the e-mail address for the login name when your users log in, instead of a DOMIAN\USERNAME login name. Ok. It also said to make sure that all of your e-mail accounts were unique in your mailboxes (i.e., that 2 mailboxes did NOT have the same e-mail address). If there were duplicate e-mail addresses in mailboxes, the OWA login using e-mail address as login name would not work (not to mention the e-mail problems).
Next, Technet article 317471 talks about the default NTFS permissions on the C:\Program Files\Exchsrvr folder that are needed for OWA logins to work. The article is here:
http://support.microsoft.com/default.aspx?scid=kb;en-us;317471
(please remove any spaces)
Lastly, Technet article 322309 talks of a bunch of settings for Exchange 2K and OWA. Take a look at this article also if needed:
http://support.microsoft.com/default.aspx?scid=kb;en-us;322309
(please remove any spaces)