I have a web service being called from a remote server and recently ran into an issue where we could not access a newly added method. The error being returned was something like this:

coldfusion.xml.rpc.ServiceProxy$ServiceMethodNotFoundException: Web service operation [METHOD NAME] with parameters {...} cannot be found.
...

After checking the remote web service for a problem several times, and outputting various different calls, I tried restarting ColdFusion to see if that would help. It did.

Shortly after, I recalled a "Web Services" menu option in the CF Administrator under the "Data & Services" heading and found a much easier approach to forcing ColdFusion to grab the new WSDL. Next to each referenced Web Service, there is a Refresh icon that can be used to force it. Hopefully, next time this issue comes up it will be a lot faster to diagnose and resolve.