Prova vedere se ottieni sempre la stessa id tramite session_id()

Puoi anche stampare i cookies per vedere se vengono inviati comunque
Codice PHP:
var_dump($_COOKIE); 
Verificherei anche se il browser accetta i cookies davvero.