come propaghi la sessione?
il fatto che generi un nuovo id di sessione ad ogni pagina mi fa pensare ad un session id non disponibile....quindi o mai generato o mal propagato.Se obblighi gli utenti ad avere i cookie attivi allora fai così:
crea un file esterno e chiamalo sess.inc(dagli il nome che vuoi) e mettici questo dentro:

ini_set('session.use_cookies', 1);//vuol dire che saranno usati i cookie per propagare la tua sessione
ini_set('session.use_only_cookies', 1);//vuol dire che sarà scartata la possibilità di un cookie passato via URL.
session_start();//nuova sessione

aggiungilo alla testa di ogni files....

Pesavo poi ...ma il server dove lavori è lo stesso per tutti gli applicativi?