I'm not sure how php-nuke works, but I've had this problem as well on IIS as well. What happens is that if a page sends a cookie header along with a redirect header, the cookie header gets ignored. There's an MSKB article about it somewhere, do a search. What I ended up doing is instead of using Header('Location: blah'), I used header("Refresh: 0;url=$url");. With IIS this causes the cookie to be sent and the page is still redirected. This may or may not be related to your problem, but it's a starting point.
Brandon Tallent
http://www.resynthesize.com/code/