change permalink format and change internal links to match

I want to change the format of my permalinks and then change all the internal references in my posts to conform to the new format. Right now if I change the format then most of the links don’t work, including those in my sidebars.