API Error OAU-222 Account does not exist

Hi, we try to authenticate through Authorization Code Flow and we get the error OAU-222 when calling the following request and using the required parameters and authenticate with HTTP Basic scheme using the client ID and client secret as login and password, correspondingly .

POST /restapi/oauth/token

code=<the_authorization_code_i_get>&grant_type=authorization_code&redirect_uri=<my_redirect_url>

We have a developer account and sandbox account and have created the app. We call the API to get the authorization code, we log in with our sandbox user and get the code correctly. However, when we call the token request to get the access token I get the error.

This is the response we get:

{
    "error": "invalid_grant",
    "errors": [
        {
            "errorCode": "OAU-222",
            "message": "Account does not exist"
        }
    ],
    "error_description": "Account does not exist"
}

Is there something else we need to do in our sandbox account? This doesn't make any sense since we can login successfully in order to receive an authorization code. Thank you.