Hmm, I couldn't find any old URLs.
Good news through. I switched my permalinks setting back to default (aka ugly) and all the projects pages now work! I don't know why. I looked through the directory and database but it's hard to see the path because there is no "projects" folder.
All I know is that the default permalink [http://example.com/?project=project1] works perfectly but the post name permalink [http://example.com/project/project1/] leads to "Page Not Found."
Is there a way to make the permalinks just for the projects be on the default setting but all the other permalinks be on the post name setting?