I got plagued by the cookies problem and none of the solutions worked. Even disabling the cookies check just meant I could not log in.
After wasting 2 hours on this, hacking the wp-login.php script to death I finally discovered the problem.
WPMU does NOT like hostnames. It only likes domains.
If you set your site domain and home options to say "myserver" cookies will fail constantly. Firefox, nor IE will accept cookies from the site.
Change all references to "myserver" to "myserver.mydomain.com", delete the cache, cookies, authed sessions and all works again.