A colleague of mine, lets call him Jereme, came across this and he suggested I post it on my blog, so here goes. One of his clients where having issues with one of their search scopes. Whenever a user would try to do a search with one of the custom scopes, they would receive an error saying "Your search cannot be completed because of a service error. Try your search again or contact your administrator for more information.". It only occurred with this one search scope.