WordPress MU

Working with subdomains, we went in and changed permalinks using phpmyadmin to whatever, now we get 404 on the posts, except if you go in and manually click the update permalink button, this is not a option with 10k in blogs and i think our users will get mad, think they are getting mad now, we had to hide cats in the url because people were using very bad cats, they now cant change them but now the sites posts are 404, is there another option that hides these or a rewrite rule that we arnt finding thank you