Update: I got it working! For now...
Rev Voodoo, nicolasleroy: Out of curiosity do you have any other Twitter related plugins installed? Take a good luck and see if you have any other plugin besides Twitter Tools that interacts with Twitter. I want to see if there's a possible correlation here.
In addition, I got mine working by disconnecting the connection in Twitter Tools again, then I went to set up a brand new app all over again. The only difference I made was not to include anything in the "Organization" field, and I didn't upload an application icon either. Trivial changes that shouldn't have made a difference at ALL, and yet this app is working successfully now. I have always set read/write access every time I created an app so that should not have be an issue either.
I tried creating a new app before with no success, I have no idea why it suddenly worked now. That's why I suspect there might be an issue with having multiple Twitter related plugins all using OAuth to access Twitter.