It might be something to do with the header() redirect. If there is a difference in the domain names used to access that page, then the session cookie may not be supplied for the redirected page. For instance, if you called the first page as http://yoursite.com/page1.php, but the redirect calls http://www.yoursite.com/page2.php, then the session cookie may not be passed, since semantically they are two different domains.
You can get around this by setting session.cookie_domain to ".yoursite.com" (note "." at beginning of the value, either in your PHP configuration file, a .htaccess file, or via the [man]session_set_cookie_params/man function, which you would need to use on each applicable page before the call to session_start().