For PHP with CGI, make sure you put the rewrite rule above any other rewrite rule you might have.
In my case, I put this at the top of the .htaccess (below RewriteEngine On):
RewriteRule .* - [E=REMOTE_USER:%{HTTP:Authorization}]
My symptom was that the REMOTE_USER (or REDIRECT_REMOTE_USER in my case) was not being set at all.
The cause: I had some other RewriteRule that was kickin in and was set as LAST rule.
I hope this helps.