I think you are going too deep here. What BPS does is very complex, how BPS does it is very, very simple. ;) I have tested wp-admin password protection on WP single sites, Network / MU sites and Giving WP Its own directory sites and all worked fine without adding the ErrorDocument 401 code. This is on GoDaddy hosting so keep in mind that every single web host has its own configuration methods / files / requirements etc and this means that most things are similar on all hosts, but then there are going to be things that are going to be completely web host specific.
Also this new .htaccess code added from "Hardening WordPress" may be a factor for your particular web host. This is not likely the issue, but you never know - different web hosts do all kinds of different things. ;)
RewriteRule ^wp-admin/includes/ - [F,L]
RewriteRule !^wp-includes/ - [S=3]
RewriteRule ^wp-includes/[^/]+\.php$ - [F,L]
RewriteRule ^wp-includes/js/tinymce/langs/.+\.php - [F,L]
RewriteRule ^wp-includes/theme-compat/ - [F,L]
Look at the simple things first:
Look at the URL's themselves and anything that does not make logical sense. So to see the problem you need to look at the specific details of what is occurring. When you see the WP message "your looking..." what URL do you see in your Address bar?
Then go a little deeper:
Do you have a standard Single site WP installation?
Ary you using "Giving WordPress Its Own Directory" WP installation method?
Are you using any other plugins that are writing to your .htaccess files?
Are you using any other security plugins that could be interfering with BPS?
Are you or your Host (some do DNS stuff automatically) doing anything with DNS?
And a final thought to leave you with - adding a second Authentication layer to an already Authentication protected directory does not make it any more secure. ;)