Sometimes containers do not seem to behave very nicely when you have an Error page handled by a servlet filter. In this case it looks like you probably have mapped "/error" with PrettyFaces, and are forwarding that internally to another resource. (PrettyFaces works with Servlet forwards)
I believe what occurs here, is the container sees that new Forward, forgets that it was actually showing an error page, and sends a 200 status because the Forwarded request was successful.
What you will need to do to resolve this, is add an <action>#{bean.send404}</action>
that sets the 404 status in your error page prettyfaces mapping.
<url-mapping>
<pattern value="/error" />
<view-id="/faces/error.xhtml" />
<action>#{bean.send404}</action>
</url-mapping>
Then your bean method will need to get a hold of the HttpServletResponse, which ou can usually get from the FacesContext:
HttpServletResponse response = (HttpServletResponse)FacesContext.getCurrentInstance()
.getExternalContext().getResponse();
response.sendError(HttpServletResponse.SC_NOT_FOUND);
That should do the trick for you.