It is just the cost of good quality. This is like suggesting you shouldn't write error handling code, because the code might change and have different errors that need to be handled.

Also if the interface doesn't change but your unit tests fail on a data structure change then perhaps your tests are too coupled.

Why would anybody doing TDD have tests highly coupled with the implementation? They shouldn't have this problem at all.

The GP diagnostic isn't good here. Those are bad tests, not tests written too early. What doesn't mean you shouldn't wait for your functionality to be accepted before testing it; some times you should; but this happens for completely different reasons.

By using TDD, which promotes isolating the changeable surface area to a small area during discovery. That way you don't have to introduce the complexities of API changes across the rest of the application surface area, avoiding the churn spoken of earlier.

Most of the time I already know what I'm going to write. Thus most of the time I can start with a simple test and it isn't too early. It is rare to be presenting with a problem in code that you don't know if it is solvable or how to solve it and jump right into code (as opposed to research, or white board discussions), which then gets enough in place that it isn't too early.