Core Tweaks will just set the permalinks for you if the htaccess file is writable from a single page where you can bulk set most of your wordpress settings at one time. Which is mostly meant for new installs.
You're likely right cupboy2013, that the rewrite rules have been removed. Did you try just setting the permalinks again? Set them back to a default setting once then set back to your preferred setting. If they're still not working, do you have ftp access to check the htaccess file to see if the rewrite rules are being added?
Otherwise, you might need to put in a support ticket with your hosting to get help with it. Some IIS hosting will not work with the permalinks not using the index.php in the url. But if they were working before, you should be able to set the reset the rewrite rules to have them start working again.