В общем проблема оказалась в конфиге php, был включен параметр mbstring.func_overload 2. А там по цепочке неправильно работал метод random_bytes, т.е. он выдавал строку, длину которой strlen считал не правильно. В итоге метод проверки валидности кук выдавал false.
Начиная с php7 композер будет выдавать ошибку, что этот параметр нужно выключить, так что сомневаюсь, что кто-то еще столкнется с этой проблемой.