If your service on app engine runnning as not "default service" and getting NOT_FOUND error, this gist will help.

cloudTasks.go

func CreateTask(projectID, locationID, queueID, relativeUri, message string) (*taskspb.Task, error) {
	ctx := context.Background()
	
	client, err := cloudtasks.NewClient(ctx)
	if err != nil {
		return nil, err
	}
	defer client.Close()

	queuePath := fmt.Sprintf("projects/%s/locations/%s/queues/%s", projectID, locationID, queueID)

	// this setting is needed if your app engine service is not default.
	appEngineRouting := &taskspb.AppEngineRouting{
		Service: os.Getenv("GAE_SERVICE"),
	}
	req := &taskspb.CreateTaskRequest{
		Parent: queuePath,
		Task: &taskspb.Task{
			MessageType: &taskspb.Task_AppEngineHttpRequest{
				AppEngineHttpRequest: &taskspb.AppEngineHttpRequest{
					HttpMethod:       taskspb.HttpMethod_POST,
					RelativeUri:      relativeUri,
					AppEngineRouting: appEngineRouting,
				},
			},
		},
	}

	req.Task.GetAppEngineHttpRequest().Body = []byte(message)

	createdTask, err := client.CreateTask(ctx, req)
	if err != nil {
		return nil, err
	}

	return createdTask, nil
}

I had following error without adding appEngineRouting.

attemptResponseLog: {
  attemptDuration: "0.016455s"
  dispatchCount: "1"
  maxAttempts: 0
  responseCount: "1"
  scheduleTime: "2021-08-04T16:32:16.465277Z"
  status: "NOT_FOUND"
  targetAddress: "POST /task_handler"
  targetType: "APP_ENGINE_HTTP"
}

You can create/update queue from command line.

$ gcloud tasks queues update fooTask --routing-override=service:bar-service-name

@super-dog-human I have the exact same error. The name of my worker function is "server" and it has a route "/log_payload" that handles the task in the queue. I don't know my service name. So this update command would look like this for me: glcoud tasks queue update testqueue --routing-override=service:server