I am having the same issue. All the RewriteRules were copied form a
different server and suddenly stopped working for unknown reasons when
moving them a Debian installation.
The 404 page that is returned says that the requested URL was not found
on the server, while it lists a file that is very much present and
readable for all users.
Are there any known workarounds for this problem, since it doesn't seem
to get fixed?