Regarding the use of WP Missed Schedule – no, I do not recommend installing it. It’s a tool which is a frequent cause of missed Tweets: it’s used if your site is routinely missing scheduled posting, but it does not run the action that will trigger Tweeting, so posts published via that method won’t be Tweeted.
I’m confident that this doesn’t have to do with any change in the Twitter API; I also doubt that it’s the WP Post API, since I would expect that to have a wider-reaching effect: this is actually a fairly uncommon problem, as far as I can tell.
But, mostly, I need more data to be able to figure out what’s common about sites with this problem.