You're right, I figured out the problem was that the web service was not a SOAP service. It is a REST service.
The problem was that I was trying to Add A Service Reference via the Visual Studio tool. This isn't possible with this type of service I was connecting to because it uses cXML and is a REST service (it works very differently).
In my solution I manually wrote Web Service REST calls by doing simple POST and GET requests and passed in the XML in string format.
This worked for me... I used this tutorial: https://developer.yahoo.com/dotnet/howto-rest_cs.html