The problem is different than I first thought. It turns out that, whilst my old permalinks work fine, if I add any new ones, there are problems. Specifically:
If I add a new page with the main page as the parent, I get a "sorry, no posts matched your criteria" message (despite the fact that the page has content in it)
If I add a new page as a child of any page except the main one, I get a "The page cannot be found" message.
This one's really stumping me - any suggestions? Thanks heaps - JB