We also experience a lot of GUI changes, but have been able to overcome with extensive framework to make tests in such a way that they do not rely on name mapping, object full names, etc. In addition to that you want to design your tests in such a way that they perform a small set of tasks/tests, then return to the start of the application or a common point where the next set of tasks/tests would be capable of starting from. Between all of that error handling is key.
No test should produce an error that will stop all tests.
I know TestComplete is sold as a record and playback of tests without requiring any programming knowledge but I honestly do not see how anyone could produce quality automated tests without first building their own custom framework.
As Marsha said, you do want your tests to "fail" when there are program changes (that is the entire goal to detect changes between versions) but this should not stop subsequent tests from running.
As they say...Back to the drawing board :).