Jeremy took pity on me and had a glance at a sample project I was using to test eXist with SOAP. It seems Visual Studio .NET's 'Add Web Reference' Wizard wasn't setting up the proxy class for the web service correctly...
The web services are at http://localhost:8080/exist/etc... but VS.NET set up the proxy classes to use http://localhost/exist/etc... Manually adding the ':8080' to the web references' server name completely resolves the connection problems I was having.