es simple, no uses header, utiliza alguna funcion de javascript o bien una etiqueta <meta> con un refresh...
Código PHP:
<html>
<head>
<meta http-equiv="refresh" content="5;URL=otra_pagina.php">
</head>
<body>
...
En ese caso se va a redireccionar a "otra_pagina.php" al cabo de 5 segundos (que es lo necesario para que el usuario lea el mensaje...)
o bien, hazlo en PHP, pero con un time tambien:
header("Refresh: 5; URL=http://www.php.net");
Mas ejemplos de header:
http://es2.php.net/manual/es/function.header.php