We've just started to evaluate TestComplete and are having very similar problems on playback of recorded tests where, seemingly quite randomly, the system fails to locate objects. If a failure does occur it seems to always occur at the same point in the playback. However, on another test the same object will be recognized with no issues at all.
It is fair to say that we've experienced very similar problems with other GUI test applications that we've tried. The problem is that unless playback is guaranteed to execute properly, then it's hard to see how the application can be of much practical use.