Cookies empeche l'access a des pages

OK, je test si le cookie existe deja, sinon je le cree...c' ca?

Pas uniquement.
Surtout que si le navigateur de l'utilisateur bloque les Cookies, tu ne pourras pas en créer.
Si comme dans ton cas, les Cookies ne sont pas autorisés (et donc bloqués) par le navigateur de l'utilisateur, tu ne fais aucune redirection et tu annules le système de connexion persistante pour l'utilisateur tout en le prévenant par exemple.
Pour faire simple, tu tentes de créer le Cookie à sa connexion et dans ton système de vérification de Cookie lorsqu'un utilisateur est déconnecté, tu vérifies d'abord si le Cookie existe avant de le connecter et faire la redirection.
Ce serait quand même plus simple si tu nous montrait du code, car là nous ne pouvons faire que des suppositions.

$req = $database->prepare('SELECT * FROM users WHERE username = ? OR email=?');
    $req->execute(array($_POST['username'], $_POST['username']));
    $user = $req->fetch();

    if($user){

        if(password_verify($_POST['password'], $user['password'])){
            if($user['validate_token'] == NULL){
                $_SESSION['auth'] = $user;
                $remember_token = $_COOKIE['remember_me'];
                $update_token = $database->prepare('UPDATE users SET remember_token=? WHERE id_user=?');
                $update_token->execute(array($remember_token, $user['id_user']));

                $_SESSION['flash']['succes'] = "You are connected";
                header('Location: index.php?page=account');
                setcookie('remember_me', $user['id_user'] . '==' . sha1($user['id_user']) . '==' . sha1($user['username']), time() + 3600 * 24 * 1);
                exit();
            }

Merci de ton aide, j'ai suivi ton conseil, et c'est resolu.

De rien.