95% of the time the issue is that you're on a shared server and your server IP is quickly maxing out it's Twitter calls. Twitter allows 150 unauthenticated calls per hour from any IP, and it wouldn't be unheard of for there to be more sites than that on your shared server and it only takes ONE that's making one or more calls to Twitter per page load to burn through all of them in a minute.
About 4% of the time it seems to be misconfigured servers that can't make calls back to themselves. If the normal WordPress cron doesn't work for you, then this is probably the issue.
The other 1% of the time is just what I allow for margin of error on my estimates. I'm sure there COULD be another issue that causes this, but I haven't seen it.
The reason you still see Tweets is because at some point it was able to connect and it stored the Tweets it grabbed. It won't get rid of those until it can successfully connect again.
In the future I may add the option to authenticate with Twitter which would allow the requests to be logged against a Twitter account instead of a shared IP, but I do not currently have a timeline for this.