WordPress MU upgrade(from 2.x to 3.2.1) was a rather simple process surprisingly! Having completed it in a matter of couple hours for a fairly large blogging network, I was a happy camper up till the moment when permalinks started giving 404s.
What followed is painstaking process where I verified everysingle aspect of configuration from Apache’s mod_rewrite setup to htaccess rules to WordPress’s network site configs. Everything looked correctly.
Googling around for a good hour I came across this site, which pointed to the incompatibility of some plugins with WP3. In my case problem lied in a plugin called Top Level Categories, which I had to disable to get the permalinks working.