Похоже, вам нужно обновить ссылку на сервис.
Перейдите к проекту, который использует службу, щелкните левой кнопкой мыши ссылку на службу в обозревателе решений и, наконец, выберите «Обновить ссылку службы».
Может быть, я ошибаюсь, и вы сделали это, но, поскольку вы не упоминаете об этом в своем вопросе, это мое предложение.