Problem med cookies og redirect

Hej Eksperter,

Jeg har en php-fil, hvor der først skal sættes en cookie, og derefter skal viderestilles til en ny underside. Men det ser ud til at cookien ikke bliver sat, når der efterfølgende viderestilles. Kan det passe?

I filen redirect.php har jeg følgende kode:
<?php
setcookie("kage", $value, time()+2592000);
$redir_url = "http://www.minside.dk/underside/";
if (isset($_COOKIE["kage"])) {
Header("Location: $redir_url");
}
?>

Men når jeg på http://www.minside.dk/underside/ forsøger at hente cookien med følgende så virker det ikke:

<?php echo $_COOKIE["tilmeldtnyhedsbrev"]; ?>

Håber I kan hjælpe.