Getting errors trying to authorize application link

Our company, CodeStream, offers a plugin for popular IDEs that allows development teams to more easily collaborate on software development. As such, we offer an integration to Jira Server (self-hosted Jira). To assist users to set up this integration, we direct them to to set up their application link, then they give us their private key and consumer key so our side can initiate an OAuth process with them and ultimately obtain an access token for the integration.

The first step during the OAuth process is to obtain a request token, then ask the user for the appropriate permissions in their browser, then exchange the request token for an access token. This works for most of our users, but for a few users, when we direct to their self-hosted Jira with the request token to get their permissions, they are seeing this error in their browser: “The request token you are trying to authorise is not valid.”

I’ve done a good deal of experimentation to try and isolate the problem but have had no luck. As far as I can tell the process of obtaining a request token works perfectly. Is there any more detailed information about what this error means and what may be going wrong here? I am truly stumped.