I have finally tracked down the issue and am working on an update right now (it will be 0.9.x) once it is really. I just wanted to let you know, apologise and explain what happened.
WordPress uses the serialize and unserialize functions, to format data in a text string, before saving data to the database. However these functions do not handle Unicode characters. I was wrongly under the impress that WordPress used the json_encode and json_decode functions, which do correctly handle Unicode characters.
My recent patches were infact not working, but for most people this was hidden. The plugin not having correctly saved the data, was fetching the Tweet data from Twitter before rendering the page. For some, still unknown, reason some sites (like yours) while not correctly saving the data in the database, were still having a half serialized return from the database, which was causing the "Sorry, no Tweets found." and "Tweet data is not in the expected format." error messages.
I believe that by me doing the serializing with json_encode before sending the data to the database and then unserializing myself when fetching it using json_decode, that I can successfully store the Tweet data for everyone no matter what is in the content.
I should have a patch out later tonight and now I can consistently reproduce the error I am very confident that this fixes the problem.