Vendría bien que pongas el código que estás usando de sesiones (donde las defines y como las pretendes leer).
A su vez .. no indicas como "propagas el SID" (Identificador Unico de sesión) pero .. por lo que describes parece que no se está propagando ..
Revisa la configuración de PHP sobre sesiones:
session.use_trans_sid .. session.use_cookies
Ayudaría tambien ver que tipo de links haces en tu menú .. por ejemplo si son links HTML normales o son javascript/flash por ejemplo .. Ya que PHP dependiendo de la configuración de las anteriores directivas . .no propaga el SID (no incrustra el SID) en redireccionamientos tipo javacript . o flash .. o header() .. entre otros.
Lo ideal para evitar problemas: de seguridad de tus própias aplicaciones y de tu código .. es propagar el SID en cookies (esto requiere de un navegador que acepte cookies .. ese es el único detalle).
más info:
www.php.net/session
Un saludo,