Two things come to mind as possibly having something to do with your problem:
1) The first thing you should see when you try to access a folder protected in this way is an authentication "pop up" box, that asks for the user name and password you set-up when you applied the .htaccess password protection to the directory via the Control Panel->Goodies section. The "Page not found" for failed_auth.html "error" message you report receiving is what you should receive if you did not successfully authenticate via the "pop-up" and have not prepared an .html file named "failed_auth.html"; in other words, what you are seeing is "normal" if you "bypassed" the authentication (by hitting "cancel" in the box, or in some other way failing to properly authenticate with the user/pass).
2) It sounds as though you are not seeing the "authentication dialog". I know you reported this behavior using multiple browsers, but there are still a couple of things you should check.
Firstly, clear your browser(s)' caches completely, as having already cached the "non protected" page can cause problems, and could account for how you "bypassed" the authentication (or at least how the server thinks you bypassed it ).
Secondly, make sure you are not allowing any "internet security" product to interfere with you seeing the authentication dialog. Properly configured, they should all let such a thing be displayed, but some of these products can be "funky" (especially anything with "Norton" or "Symantec" in the name!). Good luck, and let us know how you make out!