Yeah, a common problem: Header() only works if you havent output anything (no whitespace, nothing) yet, since any output would send the standard http headers.
So, put the session_start() and redirect in case of false / no login at the very top of the page. skip the else part, since it is only reached if there's no redirect anyway and simply add the menu where you want it with the include directive.
No idea about the session cache limit if you're only using this one variable. You could replace it with $SESSION["SESSION"] = "yes";
and isset($SESSION["SESSION"]) or sth like that though.
If you're storing other information in the session, maybe there's too much of it. Some servers have limits on the how much is allowed in a single session, esp if it is not stored in temporary files but in memory.
G.