Гм. Ну либо используй кэширование вывода, либо меняй куки не header'ом, а с помощью html или javascript. Пару страниц назад был такой вопрос и на него достойно ответили