PayPal Permissions Service -> RequestPermissions CURL example from sandbox returns an error 500000 response

I used to try PayPal Permissions Service using this guide: https://developer.paypal.com/docs/classic/permissions-service/gs_PermissionsService/#call So, according the guide, I executed the following CURL command from the example:

    curl https://svcs.sandbox.paypal.com/Permissions/RequestPermissions \
      -s \
      --insecure \
      -H "X-PAYPAL-SECURITY-USERID: caller_1312486258_biz_api1.gmail.com" \
      -H "X-PAYPAL-SECURITY-PASSWORD: 1312486294" \
      -H "X-PAYPAL-SECURITY-SIGNATURE: AbtI7HV1xB428VygBUcIhARzxch4AL65.T18CTeylixNNxDZUu0iO87e" \
      -H "X-PAYPAL-REQUEST-DATA-FORMAT: JSON" \
      -H "X-PAYPAL-RESPONSE-DATA-FORMAT: JSON" \
      -H "X-PAYPAL-APPLICATION-ID: APP-80W284485P519543T" \
      -d '{
          "scope":"EXPRESS_CHECKOUT", \
          "callback":"http://www.example.com/success.html", \
          "requestEnvelope": { \
            "errorLanguage":"en_US" \
          }}'

After executing, I have received following response:

{"responseEnvelope":{"timestamp":"2016-03-25T02:50:04.278-07:00","ack":"Failure","correlationId":"591d6ec4ce914","build":"2210301"},"error":[{"errorId":"500000","domain":"PLATFORM","subdomain":"Application","severity":"Error","category":"Application","message":"Internal Error"}]}

And that confused me a lot. Naturally, I tried it out with my own sandbox credentials. If I'm changing USER_ID or PASSWORD fields, I'm getting an "Unauthorized" error, but when I replaced SIGNATURE field with a wrong value, the response remained the same. However, the signature I have is a right one, and it works correctly with my ExpressCheckout sandbox app.

Are there any ideas where I could be wrong, or is it a PayPal issue? What should I do to make this functionality work in my case?

Thanks.