I think all that's saying is that you said "require valid-user" in your .htaccess file, and the authentication data supplied didn't meet that criteria. Incidentally, have you tried that with an upper case "R" at the beginning? eg. "Require valid-user" rather than "require valid-user" ?
Could it simply be that the username/password combination in your .htpasswd file have invalid characters?
You could try changing it to read something like
Require user <username>
Where obviously you replace <username> with the, erm, username!
You may get a different error if it's a .htpasswd problem, which might give you more of a clue!
Sorry I can't solve it for you, but I do try ;-)