Pretty permalinks break site

I've been running MilkChic Breastfeeding Fashion with pretty permalinks with no issues for some time and have just realised that over the last couple of days everything has started redirecting to the homepage. I can't figure out what on earth has caused the problem but this is what I have already tried in an attempt to fix it:
1. Reset permalinks in settings - going to p=123 structure fixes the categories but changing back breaks it again.
2. Updated Wordpress to latest version and tried again - no effect
3. Switched off Hummingbird caching - no effect
4. Deactivated Hummingbird entirely - no effect
5. Deleted .htaccess and used autogenerated version, then repeated the above - no effect
6. Deactivate all plugins - no effect

I don't know where to go next and don't want to leave my site on the standard structure as I've been working really hard on my SEO and am seeing results. Please can someone help me with this. I've enabled support in my dashboard and am happy to provide FTP details if needed.

Thank you!