How are you referencing the service? With what http address? If you are doing this in VS2005+ you might need to set up your site in IIS to expose it properly. Although I think as long as you are working in localhost, even the development web server should be visible by VS for a service reference, after all, Internet Explorer can obviously see it.
-Peter
compiledthoughts.com