Ha! Figured it out. It was my bad.
After you create your application with the Twitter api, DO NOT immediately create your access token. Instead, go to "settings" and change the application to "read and write." If you skip this step, the default is "read only" and you will not be able to post anything to Twitter. You can see if this is your problem by going to your application and seeing if it says "Access level read only" under "Your access token."
To fix this, you have to delete the whole application from the Twitter API since you can't delete and recreate access keys. Create a new application, this time making sure you set the application to "read and write" in the settings tab before creating the access key. Then in the wordpress you'll need to go to the plug-in and disconnect from Twitter. Then you'll need to reenter the new information from your new application.
If that doesn't work then you might want to check your server time. If it is >5 minutes different from Twitter's system time it won't work until you fix your server time.