No puedes enviar nada, nada de contenido de texto antes de poder enviar un header() en este caso todo tu HTML es texto, por eso tienes que mover el proceso a antes:
Código PHP:
<?php
if( hay_datos_post() ) {
// compruebas todos los datos
insertar_bdd();
if( insertar_exito() ) {
redirigir();
}
}
// a partir de aqui todo tu HTML
?>
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd">
Saludos.