I had the same but have figured it out as it applies to my server configuration on Linux running Plesk CP. Hopefully by sharing this helps someone else out.
2 Steps required.
1) If you are using Plesk Control Panel then in Setup >> look under Services for: PHP Support - make sure (PHP 'safe' mode on is UNCHECKED)
2) In WordPress Dashboard go to Settings >> Permalinks - Select your Common Settings preference and click Save Changes button. You will then see the following message:
"If your .htaccess file were writable, we could do this automatically, but it isn’t so these are the mod_rewrite rules you should have in your .htaccess file. Click in the field and press CTRL + a to select all."
Underneath is a block of code that you need to save and create an .htaccess file (save this text file as .htaccess). Then upload this to your Root of your Web Hosting server via FTP.
That should do the trick.