bueno, este post es algo viejito, tanto que ya aprendi a validar y todo eso, jejeje, bueno, al grano, la validacion y el procesado de los datos los hago en la misma pagina, nunca he probado enviar nada a otra pagina, creo que se complica asi el envio de mensajes de error, seria algo asi:
  Código PHP:
    <?php
if(isset($_POST['enviar']) && $_POST['enviar'] == 'Enviar'){ // verifico si es enviado el form
    if(!empty($_POST['nombre']) && $_POST['apellido']){ // verifico que los campos no esten vacios
        $nombre = $_POST['nombre'];
        $apellido = $_POST['apellido'];
        // hago la consulta
        $insert = mysql_query("INSERT INTO tablaUsuarios bla bla bla.....");    
    }else{ // en caso que esten los campos vacios, envio un mensaje de error
        echo "ERROR...! Debe llenar todos los campos del formmulario";
    }
}
?>
<form name="usuarios" method="post" action="<?php $_SERVER['PHP_SELF'] ?>">
    nombre:
    <input type="text" name="nombre"><br>
    apellido:
    <input type="text" name="apellido"><br>
    <input type="submit" name="enviar" value="Enviar">
</form>   
  es mas o menos asi, hay otras cosas que debes ver, como que si se llena un solo campo, que el otro no pierda el valor que tiene, eso se resuelve asi: 
 Código PHP:
   
<input type="text" name="nombre" value="<?php echo $nombre ?>">   
  pero si pasa bien el form, debes destruir luego las variables, para que no te ponga los valores nuevamente, y no digo mas porque me estoy enredando y no quiero enredarte a ti 
 
saludetes y suerte claro