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)