--- a/taskcluster/taskgraph/optimize.py
+++ b/taskcluster/taskgraph/optimize.py
@@ -40,17 +40,17 @@ def resolve_task_references(label, task_
     def repl(match):
         key = match.group(1)
         try:
             return taskid_for_edge_name[key]
         except KeyError:
             # handle escaping '<'
             if key == '<':
                 return key
-            raise KeyError("task '{}' has no dependency with label '{}'".format(label, key))
+            raise KeyError("task '{}' has no dependency named '{}'".format(label, key))
 
     def recurse(val):
         if isinstance(val, list):
             return [recurse(v) for v in val]
         elif isinstance(val, dict):
             if val.keys() == ['task-reference']:
                 return TASK_REFERENCE_PATTERN.sub(repl, val['task-reference'])
             else: