This was actually a simple issue of permissions on the deployment environment.
Using the Code Access Security Policy Tool (Caspol.exe) it was just a matter of applying the correct permissions. There's a how-to-use guide on msdn.
The actual command line string was
CasPol.exe -addgroup 1 -strong -file D:\deployment_location\WcfServiceHost.exe -noname -noversion FullTrust
This was performed on a collection of services. Since our version numbers were changing frequently using the 'noversion' was helpful, the service also required FullTrust in our setting.
To re-use the fix for various machines, create a PowerShell script (or batch file) and using the 'polchgprompt' parameter to turn off prompts so the script can execute without intervention.
polchgprompt - "Enables or disables the prompt that is displayed whenever Caspol.exe is run using an option that would cause policy changes."
Script Structure:
CasPol.exe -polchgprompt off
--all the individual service calls--
CasPol.exe -addgroup 1 -strong -file D:\deployment_location\WcfServiceHost.exe -noname -noversion FullTrust
...
CasPol.exe -polchgprompt on