Alright.. thanks for the updated screenshots. Fixing the Login setting was definitely critical, but obviously still not working. We tested with a known-good API key and the same issue happened.
The only thing that leaves is something we haven't run into before, but could be the problem.. your system clock. It may be a long shot, but can you check that your time is correct for both your timezone and the actual time? When performing authentication, your server time needs to 'sign' its requests within 5 minutes of Twitter's time. If not, that error can apparently occur. It doesn't look like there's any way (that I know of) to check your time in the Joomla admin area, so this may be a moot point.
If that doesn't help, the next step would be to ask for FTP credentials, if possible, so that we can edit our authentication code and check what's being generated to make sure it's not something even more bizarre occurring on your site.
We'll get you going, and sorry for the troubles!
Alex