I did figure it out.
There is a collection named "AutomationStateDefinition" in Mongo "Analytics" DB. It is supposed to be filled with all Automation States of all active Email Campaigns. It was empty on the new installed environment because I didn't copy Mongo Databases to the new environment, I just wanted them to be empty. However if this collection is empty Sitecore is not able to update the "Fact_AutomationStatesStatisticsByMessage" SQL table.
 Actually the log saying something like:
"ERROR Unable to get automation state definition"
That might be a problem when you install new environment. The solution for me was deactivate and then activate each Email in EXM. The Mongo "AutomationStateDefinition" collection is filled with records once you activate EXM Email.