He probado tú código y me funciona bien.
Si quieres ver lo que estas mandando en la misma página agrega algo así
Código PHP:
<?php if (empty ($_POST["apellido"]) && (!$primeravez)){
echo "<tr><td></td><td>¡Debe introducir su Apellido!</td></tr>";}
else echo $_POST["apellido"];
?>
Para cada uno de los campos y veras.
Si no te funciona tal vez sería tu versión de php.