I just tried to replicate the problem on my WordPress. What i did was i delete my .htaccess file and this caused all of my pages to return a 404 not found, only my home page worked.
I decided to delete my .htaccess file and then I went to admin area: Settings > Permalinks and changed it to default, and saved changes
I then changed my permalinks back to the setting i wanted which is custom:/%category%/%postname%/
I then went into my FTP and checked to see if the .htaccess file had been recreated by WordPress, and it had been. now all my pages are working again.
This may seem like we are repeating the last steps i asked you to, but in this case the major difference is that we are first deleting the .htaccess file. Please make a backup of the .htaccess file just in case
Let me know how it goes, i hope this works