Sigh, the patterns and practices employed by the Microsoft Patterns And Practices team that's responsible for the Enterprise libraries are pretty deplorable. Well, the exception is accurate, you cannot call a method that's decorated as "I'll definitely check security" from code that's decorated with "Meh, I won't check security so don't bother burning the cpu cycles to check it". Which scales about as well as exception specifications as used in Java. CAS is incredibly useful, but diagnosing the exceptions is a major headache and often involves code that you don't own and can't fix. Big reason it got deprecated in .NET 4.
Editorial done. Taking a pot-shot at the problem, you need to find out why CAS is being enforced here. The simplest explanation for that is that the service doesn't run in full trust. The simplest explanation for that is that the client didn't install the service on the local hard drive. Or is generally running code in don't-trust-it mode even on local assemblies, a very paranoid admin could well prefer that. That needs to be configured with Caspol.exe, a tool whose command line options are as mysterious as CAS. Pot-shooting at the non-trusted location explanation, your client needs to run Caspol as shown in this blog post. Or just simply deploy the service locally so the default "I trust thee" applies.
Editing in the real reason as discovered by the OP: beware of the alternate data stream that gets added to a file when it is downloaded from an untrusted Internet or network location. The file will get a stream named "Zone.Identifier" that keeps track of where it came from with the "ZoneId" value. It is that value that overrides the trust derived from the storage location. Usually putting it in the Internet zone. Use Explorer, right-click the file and click "Unblock" to remove that stream. After you're sure you can trust the file :)