Hiya,
We've developed several tools that request users grant access to their Canvas account (grant a refresh token) and in our experience we haven't found the refresh tokens to expire.
Could it be that your developer key has scoping enforced and you've recently changed the scopes you request for a token? This will cause Canvas to refuse an access token for a refresh token that had a smaller set of scopes.
And it's not that you're doing some development against the beta/test Instructure cloud instances and over the weekend they got re-synced with production and so lots the refresh token you'd setup?
Users can manually revoke their tokens through https://instance.instructure.com/profile/settings, are you still able to see the application listed on the user in questions profile?
Good luck finding the cause.
Matthew