Cannot run the macro 'Solver.xlam!MainEx'

Hello, I recently upgraded Excel to 2019 version, and when I tried to start Solver I get the message "Cannot run the macro 'Solver.xlam!MainEx'. The macro may not be in this workbook, or all macros are disabled" (Or something like that). I tried everything I could find online, my macros are enabled, I ticked "Solver" in VBA ->Tools->Preferences, the file is saved with *.xlsm extension. I also recorder simple macro and executed it, no problems with that.
It is strange also that other add-ins using macros are also not working, like Euro currency tool. Not that I've used it, but I just added it along with solver to see what will happen.
Any help?