Intenta dos cosas. Una dejandolo por defaul:
setcookie("UserId", $_SESSION['UserId'], time()+2592000) ;
Y la otra, dandole el root como inicio:
setcookie("UserId", $_SESSION['UserId'], time()+2592000, "/") ;
Igual por ahi sacas algo de
http://ar.php.net/manual/es/function.setcookie.php
PD: Supuestamente, por lo que recuerdo, esto se lo especificas si queres que se ejecute en un dir especifico, si no se lo pones, se ejecutara en el dominio.