The last time I tried, overloading a web method wasn't possible, or at the very least a pain in the neck. Not sure if much has changed since I tried. Since you have clients using it, it would make more sense to just create a new web method and let them know that it exists instead of having them change code to call the existing ones.