Ive just changed the permalink structure for my entire site, with automatic 301 url rewriting from the old url to the new url.
I used a plugin called ylsy_permalink_redirect
I used it to change the old permalink structure
if you try to access the old permalink then the plugin will auto 301 you to the new url. pretty neat. (ive just implemented this from scratch for our system at work for all the major sites we have, and it proved to be massively beneficial)
the reason for doing it was that I setup my site to use the year, month, day and postname in the urls – effectively every post was 4 directories deep. not good. (well, not bad exactly, but not ewasy to remember!)
ill monitor this in a google doc spreadsheet once a week for a few months and then report on it =)