using wp_redirect to redirect to a permalink

Because it is looking for the page 404, which is a child of the page /error. Try just doing this:

function show_404($message="page not found"){
   wp_redirect(home_url() . '/error?m=' . urlencode($message));
   exit();
}

But your doing it wrong.

You should just use WordPress’s internal 404 page, it will save a lot more headaches that will arise in the future. It is as simple as creating a template of 404.php in your current theme directory.