Probably the oEmbed calls to Twitter’s API are failing on your server. This has nothing to do with the plugin since it’s all handled by WordPress itself. Also the first two methods you described don’t need the plugin to work at all, they’re part of WordPress core 🙂
Well I removed it and it works again now. How could the calls fail?
Twitter has a hard limit on the oEmbed (and other) end-point which rate limits by IP address, like 150/hr. If you share an IP address with other folks, like when on a shared hosting plan, and if they’re also using something similar (not necessarily WordPress) to grab tweets, you’ll run into that limit very quickly. A solution is a dedicated IP address.
Version 2 of the API has different rate limiting, but version 2 does not allow anonymous calls at all, which introduces a whole new level of complexity, for the little benefit it will bring.
You can install a plugin such as Core Control and look at its HTTP Access Logging module to see how and why exactly oEmbed calls are failing.
Hope this helps!
