David Prinz, once you created that service, did you save and 'cancel edit' the Thing? Usually, this error occurs if you create a service and don't save the Thing (since it doesn't know a service exists yet).
Yeah, the service was not saved. It's possible in ThingWorx to Close a service that you wrote but not have it saved (yet.) You just need to press Save and you should be good. Otherwise, how ever you are invoking the service call may be pointing to the wrong thing or entity. For example, if you write a service on a ThingTemplate, it's not exposed on the ThingTemplate, it's exposed on any and all THINGS that you have made from that ThingTemplate. Just a thought.