mám úplně stejný problém (Debian squeeze).
Dle dokumentace zápis 404.php není povolen (a je tudíž pravděpodbně interpretován jako "404.php").
Když tedy zadám /404.php (nebo různé další varianty začínající lomítkem), vyplívne mi to standarní 404 Apache ale navíc s řádkem
Additionally, a 404 Not Found error was encountered while trying to use an ErrorDocument to handle the request.
Není na to potřeba ještě něco povolit?
Nebo to tam teda narvat absolutně použitím nějaké interní proměnné, jako http://$ServerName/404.php ?