What got the code working for me was adding the server's certificates to my windows Trusted Root Certificate store and using what seems like the older way of accessing the API where you add a service reference to the config and use the following code.

var applicationClient = new Application25ServiceReference.ApplicationClient();
//Create a channel from the client and inject the token.
applicationClient.ClientCredentials.UserName.UserName = "eaxmpleuser";
applicationClient.ClientCredentials.UserName.Password = "examplepassword";
var version = applicationClient.GetVersion();

Thanks for closing the loop Adam... It does look like you switched to ASMX-SOAP (with proprietary authentication) instead of WCF-SOAP (with WS-Trust authentication.

Thanks for closing the loop Adam... It does look like you switched to ASMX-SOAP (with proprietary authentication) instead of WCF-SOAP (with WS-Trust authentication.