I just starting having this issue with the PageCriteriaQueryService.FindPagesWithCriteria.
It works well on my development machine, local sql server and website, even when I grab the test database it all works fine. I can point my local site the test database and then it fails also.