Buenas
Pues sólo se me ocurren 2 cosas más:
Una, que compruebes la configuración del php.ini y verifiques que las sessiones están bien configuradas, comprueba que existan los directorios, etc. ("Edición / Buscar" por "session" e irás encontrando opciones interesantes...). Por ejemplo:
Código PHP:
session.save_path = "C:/php-5.2.5-Win32/sessions"
session.use_cookies = 1
// etc etc etc
Si todo está bien, entonces yo iría haciendo "echo" por todos lados comprobando que lo vaya haciendo todo bien. Cuando creas la session haz también un echo de "Creo session" y muestras su valor también. Cuando le metas un valor a la variable $_SESSION haz justo después otro echo... Ve marcando todos los lugares y a ver si encuentras alguna incongruencia o algo que delate el fallo.
Personalmente no sé que más decirte, mucha suerte y un saludo!