Did you remember to die() after sending the header? The 404 header doesn't automatically stop processing, so it may appear not to have done anything if there is further processing happening.
It's not good to REDIRECT to your 404 page, but you can INCLUDE the content from it with no problem. That way, you have a page that properly sends a 404 status from the correct URL, but it also has your "what are you looking for?" page for the human reader.