Хммм... А в браузере cookies-то включены?

Очччень странно...
У меня были проблемы с кукисами, но только с отключенными в браузере...
Расширение пишешь? Если да, то скинь наработки и адрес сайта с которым работаешь мне в ПМ. Попоробую помочь.
З.Ы. Наработки - минимальный код, который не работает в конкретной ситуации. На тот случай, если не хочешь раньше времени раскрывать весь код.

Удалось залогиниться, правда решение не слишком изящное
Сначала
   var url="http://ukraine.tribe.net/local";
   var xrequest= getXMLHttpRequest();
   xrequest.open("GET",url,false);
   xrequest.send(null);
А потом уже логин
   var loginUrl="http://ukraine.tribe.net/home";
   var data = "loggingIn=1&action=TribeLogin&email=******%40*-********.com&password=*********";
   var loginRequest= getXMLHttpRequest();
   loginRequest.open("POST",loginUrl,false);
   loginRequest.setRequestHeader("Content-Length",data.length);
   loginRequest.setRequestHeader('Referer','http://ukraine.tribe.net/local');
   loginRequest.setRequestHeader('Content-Type','application/x-www-form-urlencoded');
   loginRequest.send(data);
   jsDump(loginRequest.responseText);

Жаль, что приходится терять пару секунд, но без этого вообще не логинится.