Então, eu não entendo muito de php. Eu vou ver o que você falou. Mas talvez seja na maneira como eu organizei o projeto.
Eu tenho a seguinte hierarquia: (em lugares li que poderia ser problema de sessao)
index.php inclui meu template.php,
template.php inclui permissoes.php (que usa sessao e abre ela [session_start])
template.php requer menu.php (que usa sessao, mas não abre ela)
template.php usa os dados de permissoes e de menu (usa sessao mas n abre ela)
index.php chama functions.php, que chama o database.php
database.php (usa sessao, e abre sessao lá)
o que acha?