You are problably here because will changing Permalinks settings in WordPress, your blog started responding with Page Cannot Be Found to any page other than your blog home page. I experienced this same issue but on my server I had two wordpress blogs. One was working and one was not. So I know the issue should not be difficult to solve.
I say not difficult, in my case it did take awhile, which is why I am adding this blog post.
In the end I needed to upgrade the version of php for the site that was not working from 4.4.6 to 5.1.6.
I hope this helps.
Chris