The problem is; I was trying to add a Service Reference, but I should have actually tried adding a Web Reference. As per this page:
Its because you picked service reference, which generates a WCF based stub, which uses different classes and a different programming model. You need to make sure you're creating a web reference, not a service reference (unless you want to use the WCF based stuff), In VS.NET 2008, the web reference option IIRC, is hidden under the advanced button on the add service reference dialog.