Well this little issue took me a while to investigate, but the skinny is this:
If you are going to add a service reference to a Sharepoint OData service (e.g. http://sharepoint/_vti_bin/listdata.svc) then make sure your Sharepoint site name does NOT begin with a number - otherwise Visual Studio will fail to add the reference.
Quick and easy, but this took quite a while for me to find, hope it helps anyone in the same situation!