I tested the plugin and it works very nice. Once activated it creates a "permalinks migration" tab in the options menu. You enter your soon-to-be old permalink structure there then you go the "permalinks" tab and select your new permalink structure. In my test I went from:
/%year%/%monthnum%/%day%/%postname%/
to:
/%postname%/
The old links to the posts with the year, month, day, and post name re-directed to the post with the new link without any issues and broken links. The plugin author states it won't affect SE rankings and you won't lose link love.
I'm off to change my links to /%category%/postname%/