Losing Media when changing permalink structure

I am trying to change my site from using plain permalinks to using the post-name. When I change that in settings I am losing all graphics in my media library.

Looking at the website I get missing images all over the place, and in the media library I get all empty thumbnails instead of seeing the proper thumbnails for the existing files. The files themselves are still there yet it seems that once the permalink structure is changed they are not accessible.

Thankfully if I switch the structure back to plain everything once again works correctly.

Any thoughts as to how I change this without losing the media?