Another commonly overlooked issue is that the service reference appends the root namespace of your project to the namespace you provide in the service configuration.
In other words, if the namespace of your service is ServiceReference1, the actual namespace that will be created will be [RootNameSpace].ServiceReference1. RootNameSpace is usually the name of your project, so in most cases you can fix it simply by appending your service reference with your [projectname.]. If the name of your project is MyProject, then the namespace will be MyProject.ServiceReference1
It is also fairly simple to open the csproj (assuming C# project) file in notepad and search for "RootNamespace" to find the root namespace for the project.