Our issue was strange - we were in talks with Twitch to rename out application (because of legal issues) and I believe that the rename had invalidated and disconnected all tokens.
The interesting this is the fact that we got 400 Bad Request instead of 401 Unauthorized as mentioned in the OAuth RFC.
Just to clarify, re-authenticating the user solved the problem.