The problem arises when some changes are made and random tests are failing and it becomes more difficult to fix.
How does it become more difficult to fix? Because you have to fix the tests, too? Don't just fix them. Use them as a guide to where to think a bit more. "This change broke that test. Is that telling me that the change broke the assumptions of that code, and that therefore the change is wrong? Or is it just that the test itself didn't expect this?" You should know which it is before you fix a test.
I think the situation you're describing here is not TDD-vs-after-the-fact-testwriting. It's incomplete-vs-close-to-complete test coverage.
I think and hope with TDD (or some sort of it) to get everyone into a discipline mode, which will lead to better tests. Coverage should follow.
Anyway, I think it's worth trying, but it needs commitment and discipline, similar to agile... it has to be tried as a team.