I remember the first time I used WCF i came across a weird error "The type name ServiceReference1 does not exist in the type Namespace.ClassName". I solved it ... but now someone has posted it. However I would like to mention that this will occur if ANY class in your project has the same name as ANY namespace in your project. Inshort ... keep your class names different from your namespace names.
Anyways. I was googling it due to other reasons. Async callbacks.
In case you cannot generate Async callback from the add service reference tool you need to set your project to output .NET 3.5.