No pongas el formulario en la misma página que procesa todo. Por qué? Porque no se puede utilizar header() después de alguna salida HTML. En todo caso hazlo así:
Código PHP:
if (empty($_POST)) {
//Aqui muestra el formulario
}else{
//Aqui guardas los datos y haces redirección
}