The previous post about this was marked as resolved so I thought I'd just make a new one. I have "resolved" it but I wanted to post it still in case other people have the same problem.
I was getting the "Notice: date_default_timezone_set(): Timezone ID '' is invalid" error on this plugin too. It's not that WordPress options are emptied as stated in the previous reply. It's that the option timezone_string just isn't available by default in (some?) multisite installations. It's empty in the db. I have checked a few of my multisite installations both old and new and it's the same. Empty everywhere.
The reason previous poster was only getting the error sometimes is that you only get the error when the plugin runs for the first time. When the data is cached you don't get the error.
Unfortunately I do not know why timezone_string is empty by default. It is empty even if you set time/date via the settings page in a particular blog. However, I was able to set it manually in the networkadmin/sites/settings.
For anyone reading this who is experiencing the same issue, here are valid timezones you can set manually via your multisite network admin.
Lastly I'll have to add that I don't know if setting this manually might have some unintended consequences so you'll have to do it at your own risk.