BO keeps redirecting me to login page at random times

[Tuxie]

I already tried to reinstall couple times but this didn't fix the problem. Basically what happens is that
when I'm browsing around BO I randomly get redirected to login.php. So for example:

-I might get redirected straight from login.php to login.php again without ever seeing the BO
-I might get redirected after clicking first time any link in BO
-I might get redirected after clicking Nth link in BO

But it always happens. Usually N is something like 1-20... Kinda weird?
It doesnt seem to have to do anything with how fast I'm clicking, if the page has completely loaded
before I click or anything...

My PHP version is 5.2.9
This did NOT happen when I installed on WAMP server on my machine.

Any ideas what could be wrong?
Also if someone has any ideas where to start looking for fix I'd be happy to do the bug hunting..

Thanks,
NRJ