Hola,
¿Has comprobado que session_name() y session_id() te devuelven valores validos?
Y de los metodos que has usado, el de javascript se ve muy raro. Tendria que ser algo asi:
Código PHP:
<SCRIPT LANGUAGE="JavaScript">
location.href='indexMsj.php?<?php echo session_name()."=".session_id()."&cat=$cat&sub=$sub"?>';
</SCRIPT>
Y el otro metodo es un caos. Por lo menos deberias quitar el <? echo de dentro del header().
Suerte.