Logon trouble with OWA

My users that have had access to OWA work fine. But new ones can't logon to OWA over the Internet. It asks for their name and password but then errors out and says "401.1 Unauthorized: Login failure" "The error indicates that credentials passed to the server do not match credentials required to logon to the server". Even though they can logon to the domain and use their own Outlook to get email. What gives?