Si te fijas en la documentación sobre settcookie() (
www.php.net/settcookie) de PHP verás que hay más parámetros que deberías tener presentes acerca del "domino" y "path" que deberías definir por si tienes problemas ...
El otro detalle .. puede ser tu proxy .. si usas una "intranet" bajo tu proxy .. a tus clientes (tus navegadores) deberías indicar "no usar proxy para conexiones locales" o algo así dicen ... así las conexiones locales no pasaran por tu proxy con los problemas de restricciones que estos podrían aplicacar sobre cookies u otros elementos.
Un saludo,