1. Ограничение на максимально возможное число кук или размер куки, у каждого
браузера свой предел (лучше не больше 20).
2. Ошибка в указании  (или не указание) времени жизни Cookie.
3. В параметрах указан неправильный domain (например не текущий).
4. Запуск .cgi скрипта не напрямую, а через SSI (из .shtml), соответственно cookie
 в заголовке воспринята не будет, выставлять нужно используя JavaScript.