Hm..
Make sure the following things:
1. The Newly added web method has the [WebMethod] attribute (This is the most common mistake). Like:
[WebMethod]
public string HelloWorld()
{
return "Hello World";
}
2. Make sure your project/web site builds after adding the web mathod.
3. Update the web reference in your client project, that uses the web service.
Hopefully, your problem will be fixed. Best of luck.