After you changed the WordPress permalink structure, it is important to make sure all old links are redirected to the new links, so that you do not lose your visitors who follow the old links.
I use Google Webmaster Tools to check the 404 File Not Found Error for missing page links. There were hundreds of missing links when I checked. Not good.
After a search on WordPress Plugin Directory, I found the “Change Permalink Helper“. It is a simple plugin (with no configuration) but works very well.
If a link to your site is not found, the plugin will find the post according to the slug and make a permanent redirect (301) to the new location.
Note: The database search for missing posts will add some workload to your site but, trust me, it is worth every single bit!
[image courtesy of Sr. X]