Функция php setcookie то работает, что нет?
Варианта 2: Пробел/перенос строки после ?>, или файл записанный с BOM. Первое лечится удалением лишних символов, второе через редактор кода - файл-кодировка-утф без бом.
Всем большое спасибо за подсказки.

Через несколько часов после этого поста куки заработали во всех файлах сайта.
Даже в тех файлах, в которых я не редактировал ни одного бита! (и вложенных в них)
Ненавижу магию, но пока проблема неактуальна.