When I was trying some of the SharePoint 2007 (both MOSS 2007 and WSS 3.0) Search Query tools available...
... I kept getting the following error:
System.Web.Services.Protocols.SoapException: Server was unable to process request. ---> Attempted to perform an unauthorized operation.
First thing to check is the current user's permissions on SharePoint.
Next make sure the Web Application is configured with Integrated Windows Authentication and NO anonymous access.
A nice feature for future versions would be preauthenticating a specified user account.