Just upgraded to 3.1 on 2 sites and had the problem where I was getting a page not found on all category links.
My custom permalink structure is /%postname%/
My Category base is Lingerie
The solution was a rogue plugin. I disabled all 18 plugins and rebuilt permalink structure. Hard refresh main page and discovered that all worked fine.
I then activated plugins one at a time and the guilty plugin was
Anyway I Hope this will help someone, don't give up ;)
PS. That plugin was the problem with my other site running different plugins and permalink structure