I got similar error some time back. Try using Postman. I tried the same request and replaced the user id and the page access token. It works fine.
Click on the Import button on the top and paste your curl request under raw. Then try running the call. If you get the same error, go to the body and modify it. Make sure you put this in the body part of the Postman request. Replace the recipient id with yours.
{
"recipient":
{
"id":"123456789"
},
"message":
{
"text":"hello, world!"
}
}
This is the full cURL call : Change Recipient ID and Page Access Token
curl -X POST -H "Content-Type: application/json" -d '{ "recipient":{"id":"1234567" }, "message":{ "text":"hello from bot" }}' "https://graph.facebook.com/v2.6/me/messages?access_token=PASTETHETOKENHERE"