2022-07 Fulfillments API Create Fulfillment throws {"errors":"Not Found"}

Hi all,

So I have recently upgraded my app to API Version 2022-07 and ran into an issue while trying to upgrade to the Fulfillment api.

URL: https://STORENAME.myshopify.com/admin/api/2022-07/fulfillments.json

Here is the payload I am trying to push:

{
	"fulfillment": {
		"message": "Your order has been shipped.",
		"notify_customer": true,
		"tracking_info": {
			"number": "XYZ123445534",
			"url": "http:\/\/fulfillmen.51tracking.com\/?track_info=XYZ123445534",
			"location_id": 123456789,
			"company": "Fulfillmen"
		},
		"line_items_by_fulfillment_order": [{
			"fulfillment_order_id": 1234567890,
			"fulfillment_order_line_items": [{
				"id": 1234567890,
				"quantity": 1
			}]
		}]
	}
}

//all ids and tracking numbers are masked

And here is the response:

{"errors":"Not Found"}

I am getting the same error with POSTMAN as well.

There is no help available anywhere and the support staff asked me to make a post here and reach out to the community.

If anyone has a clue about this error the please help.

Thanks

EDIT: The orders which I have tried to fulfil are there.