Twitter module Oauth 'TwitterException' with message 'Unauthorized'
This just started working with no change- I can only assume it was a temporary problem with Twitter at the time.

To some degree a useless answer, but the question gives others a list of things to try in the same situation and allows me to mark this question as resolved.