EWS 401 Unauthorized - But only when running under a service on the target server

EWS 401 Unauthorized - But only when running under a service on the target
server

I have written a windows service in C# to automatically poll an exchange
mailbox using EWS.
On my development machine, which is connected to the exchange server
network via VPN, it works perfectly.
On the target server the EWS is returning Request failed. The remote
server returned an error: (401) Unauthorized.(The remote server returned
an error: (401) Unauthorized.)
On the same server, I can connect to the EWS URL via a browser using the
same credentials as are being provided to the service.
The credentials are provided in the app.config file, and I have triple
checked that they are the same on the target server as my development
machine.
What could be causing this?