Al final me respondo yo mismo, segun parece era por tener direcciones amigables
www. dominio.com/Madrid.html,
www. dominio.com/Pamplona.html, ...
En un principio lo resolvi, cambiando un poco el codigo a:
Código PHP:
setcookie("Localidad",$Localidad,time()+31536000,"/","www.dominio.com");
Gracias a todos los que habeis intentado ayudarme, ya fuese poniendo algo, o solo leyendolo pero sin responder por no saber la respuesta.
Saludos.