In the case of someone compromising your Twitter account, the remedy is:

1) Change your password, thus locking the attacker out of your account.
2) Go into your authorized Twitter applications (on the Connections tab) and deauthorize any applications the attacker has authorized.

Again, if you are indeed correct that "most users" (and not just you and others like you) think changing your password will deauthorize all previously authorized applications through OAuth, then this is a user education issue, one that I would fix by adding a link to the Connections setting page on the password changing page with text that explains that "changing your password does not deauthorize any previously authorized applications. To do that, go to [link to Connections page]".

I will say it outright: deauthorizing ALL OAuth tokens on a password change completely negates the value of OAuth. Period.