This definitely sounds like a Permalink problem. Disable any caching plugins on the site. Then, go into the Permalinks settings. Check that the settings are what they should be. Resave them regardless of whether you had to change anything or not.
If this does not fix the problem, then use FTP and rename the .htaccess file. Now, go into Permalinks and resave them. Do the bad pages work now? If so, there are problems in the redirects in the .htaccess file.