А какому пользователю права выставлялись?

Собственно попробуй выставить пользователю ASP_Net или IIS_HostName права ( я не помню точно какому пользователю, но мне кажется, что к первому).
Еще есть вариант завести нового пользователя, дать ему права.
Указать в web.config элемент
<identity  impersonate="true"  userName="UserName"  password="Password"/>
, где указать соответственно имя и пароль.
После этого твоя веб служба будет обращаться к сетевому ресурсу под указанным пользователем.

Когда ты обращаешься к локальному хосту, ты обращаешься под system, а это максимум привелегий. Но когда ты обращаешься у другому хосту, SYSTEM тебе уже ничем помочь не может. Поэтому и нужно знать под каким именем работает твое .NET приложение. В .Net 1 это мог быть SYSTEM или ASPNET в зависимости от настроек в machine.config. По .Net 2 я тебе не смогу точно сказать. Если работает под ASPNET, то тебе нужно сихронизировать пароли на локальном хосте, так и на удаленном. Если пользователь SYSTEM или ASPNET не устраивает, то нужно вводить имперсонализацию, об этом я уже писал выше. Только обрати внимание пароль у пользователя на локальной машине должен совпаадть с паролем на удаленной машине.