How did the mocks do the damage? Lack of integration tests, wasted time, or something else?

Yes, the biggest problem was the lack of integration* tests: you can get a false confidence that everything is working, but you only know that the individual cogs are built to spec, not that the machine is working.

Second problem was that refactoring became much harder, because the tests were deeply tied to the implementation (are methods X, Y and Z called with such and such arguments?).

* using the definition of "integration" as "integrating components of the project", not "integrating with external services" (which is the definition I personally prefer).

It results in tautological tests.

Not really. I mean, you're still testing that the compiler works and that the memory works. ;)