WordPress won’t keep me logged in

I have a HUGE problem with WordPress and it started after I upgraded to 3.0. I log in to wp(with the remember me option crossed), it logges me in fine, I check out the site, leave a few comments and when I try to re-enter wp-admin it tells me i need to log in. This is what happens when I use Firefox. On Opera the problem is much worse, I log in, I visit the site without leaving any comments and when I try to enter the admin panel it tells me I’m logged out. Sometimes it loads just parts of the admin panel and the rss feeds from the dashboard tell me I need to log in.
I set up another wp 3 blog and installed all the plugins I have on my main blog but I could not replicate the problem.
I suspect it’s a cookie issue of some sort but I can’t get it solved..