Because I couldn’t find this suggested in any of the questions I looked through for this, adding my case here:
I had this problem when I manually changed the namespace in the file MyService.svc.cs, and did not change the Service name in the corresponding file MyService.svc – turned out that it needed to be Service=”namespace.classname”.