Problema com sistema de login com cookies

Bom, quando ele autentica o login, confirma senha, etc. O sistema faz o seguinte:

setcookie("logado", md5('positivo'));

setcookie("login", base64_encode($login));

require_once('teste.php');

Esse teste.php é onde ele vê se o usuário está logado, é uma página privada. Porém, o que acontece é o seguinte: Na primeira tentativa de login ele simplesmente não loga, na segunda, loga. O teste.php tem um arquivo "proteger.php" que verificar a existência do cookie "logado", caso contrário retorna pra index. O que acontece é: Primeira tentativa vai pra index, segunda, vai pra página teste.php certinho. O que pode ser?

PS. Eu sei dos problemas de se usar cookie pra login, mas o cliente bateu o pé que queria assim :mellow: