I found this thread while looking for a solution to this problem with Blackberry accessing a Sharepoint site. With Windows Sharepoint Services 3, it's easy to get past this error message if you're willing to allow plain text passwords.
- Load Sharepoint Central Administration.
- Go to Application Management | Authentication Providers
- Select the appropriate web application from the drop-down list at the top right (don't skip this step or it won't work).
- Click the authentication provider in use (probably Default).
- Under IIS Authentication Settings, put a tick in "Basic authentication (password is sent in clear text)".
- Save your changes and test.
Cheers,
Reg Natarajan