Clear all existing wordpress cookies?

I’ve been having some serious login issues with our upgrade from WPMU 2.9.1.1 to WP 3.0.1 with multisite. A large number of our users can’t login to our site anymore since the upgrade; they enter their username and password correctly and it just refreshes to show the login screen again.

I’m thinking it has to do with some incompatibility between the way the old WPMU cookie was set and the new WP multisite cookie is set. I’ve found that sometimes we’re able to get it working properly by going in and deleting all the cookies set by our domain. What I’d like to do is add some code that clears out all existing cookies whenever the login form is shown for the first time, or at least provide a link to a separate script that accomplishes this.

I’ve tried variations of this:

foreach ($_COOKIE as $key => $value) {
        setcookie($key, '', time() - 3600);
} // end foreach

with no success – the cookies remain. Any suggestions?