I came up with this method after not finding a fix that works for weeks…
If you want to change permalink structure and keep the Facebook likes for your old posts, the following method seems to be the only feasible way. (301 redirect does not transfer Facebook like box count – http://www.stateofdigital.com/the-problem-social-buttons-301-redirects )
1. Record all the old posts’ URLs
2. Install “Custom Permalinks” plugin – https://wordpress.org/plugins/custom-permalinks/
3. Change permalink structure
4. Change the old posts’ permalinks (new permalink structure) back to their URLs (old permalink structure) – so your new posts will follow new permalink structure, and old posts will keep their old permalink structure
5. Get back the Facebook likes!
This will take a lot of time if you have a lot of posts, but it works.