InfoPath cannot save the following form. This document library was either Deleted or renamed

I have faced this issue recently on my new SharePoint 2013 server. The scenario was when I publish the form to a library, the form creates the library, but when I click OK on the error message window the Library disappears from the site.

To workaround this issue

1. Install Desktop Experience Feature

2. Reboot the server
3. After that start Themes service form Windows Service Console

Hope this helps.