Yes, most of these cleaning utilities cause more issues than they solve. My bet is that’s what caused the issue.
Good news that you have TimeMachine running, so it sounds like recovery should be without too much pain.
If you feel you must use something like Clean my Mac or similar product, then I suggest you follow these steps @isaiah outlined on a simular post about Dr. Cleaner a competing product: