mm Podría ser .. asegurate de no tener esa cookie dando vueltas en tu PC de pruebas ...
Pero .. la mejor forma de comprobar si una cookie se ha guardado en el cliente es "leerla" ..
Para eso .. recuerda que las cookies (así como las sesiones) no quedaran disponibles hasta que recargues la página .. por ende, puedes hacer algun script que se llame a si mismo tras hacer el setcookie() para que lea la variable de la cookie .. si está registrada .. sigues adelante .. sino, .. avisas que en ese PC no se pueden usar cookies bla bla bla ..
El redireccionamiento automático lo puedes hacer via:
Código PHP:
header("location: pagina.tal");
exit;
Un saludo,