Un'altra cosa che potrebbe essere utile è che ho due pagine "anomale", cioè pagine che non vengono visualizzate, ma eseguono delle operazioni e poi chiamano delle pagine in base all'esito, una di queste è la login, che controlla sul database e se l'utente esiste fa una redirect sulla pagina di benvenuto, altrimenti su quella di errore.
Prina di inviare l'header location per il redirect, fa attenzione a richiamare http://www.php.net/session_write_close ed aggiungi il SID all'url usato per il redirect in modo da garantire la propagazione della sessione.

Il tuo codice, se non è messo nelle pagine incluse, funziona anche da me.
Hai creato i due file come indicato (index.php e menu.php)?
Richiamando index.php, cosa viene visualizzato?