Setcookie/php-redirection conflicting with W3 Total Cache

I have a simple setcookie and redirect code that works fine for logged in users (who aren’t cached) but it doesn’t work for non-logged in users (who are cached). W3 Total Cache is conflicting with this code, and even when I tell W3 Total cache not to cache header.php it still doesn’t work.

<?php
if(is_front_page() )
{
if( !(isset($_COOKIE[‘sitecookie’])) )
{
header(“location: /popular”);
}
}
?>

<?php
if(is_front_page())
{
setcookie(“sitecookie”, “CookieValue”, time()+10368000);
}
?>

What’s weird is a similar version of this code was previously working even with W3 Total Cache turned on, but I made some changes to the site so I needed to adjust the code and now even if I tried putting the old code back in, the setcookie and redirect no longer work.