So you are able to navigate via a web brower to the web service from the other machine with no problems, but you cannot execute the web service? What type of security are you using for the web service? Windows Integrated? Maybe you have a different domain privilage that your users.
Did you try creating a quick InfoPath form on the other persons machine and then make a data connection to the web service? That may lead to some information...
Jason
http://www.k2distillery.com/