When retrieving a UserProfile via UserProfileManager in a webservice, you need to change the value for 'HttpHandlerSPWeb' in the HttpContext.Current to your web. Otherwise no profile and you will get 'Operation is not valid due to the current state of the object'. Not a very helpful message.
if (HttpContext.Current != null)
{
HttpContext.Current.Items["HttpHandlerSPWeb"] = new SPSite(serverurl).RootWeb;
}
And don't forget to run the code to retrieve the profile with elevated privileges.