Hola,
realmente es necesario que las cookies sean lo primero que se establece en una página php. Te explico: las cookies forman parte de la cabecera de una página html con lo que deben ir antes de cualquier código html.
En tu caso, puedes hacer varias cosas para evitar el problema.
1. Montar el código html en una variable que alfinal o cuando tú quieras muestras al browser:
$html = "<html><head>bla bla bla.....";
....
$html .= "<table><tr>lo que sea bla bla .....";
Ahora validación de usuario con cookies + establecer cookies
y después tachán! :
echo $html;
2. También puedes montar la validación de los usuarios al principio de la página php que es lo más elegante/óptimo.
Si te puedo ayudar más dímelo.
Un saludo
PW
http://jcasamitjana.blogspot.com/