Re-saving permalinks solves the issue.

• Go to : Settings > Permalink
• Select your preferred format
• Click ‘Save’

If still no luck you may need to update your .htaccess file manually.
This is a server side issue and outside the scope of theme and theme support. Google has much info on how to update .htaccess file manually to fix the issue.
If you are not sure how to achieve it, drop a support mail to your hosting.