A couple of things...
The most common mistake is to forget to give "Everyone" (or "Domain Users") access to the "Log on Locally" right on the OWA Server itself. Clients actually logon to the OWA Server and establish a connection from there to the Exchange Server.
Don't know if you're on NT4/W2K, so I'll assume you know how to change "User Rights". If Admins are working, but regular clients aren't that would explain the error-since by default the "Administators" NT group is assigned "Logon Locally" rights.
If you took the defaults when installing Exchange on top of IIS, you shouldn't need to troubleshoot "Web Permissions" (Service Accounts or "\C$Exchsrv\Webdata"), but if not verify the Service Account used is correct, and that in the Virtual Directory Tab (MMC Exchange Page) that at least "Basic Authentication" is selected.
Also in the "Virtual Directory" Tab, disable the "Index this Web" setting. OWA doesn't need this option (it will help performance), but it won't make a difference in terms of "operation". Just a preformance suggestion.
Hope this helps...
Matt