We have been receiving numerous queries related to record and playback in Coded UI Test. In most of the scenarios, some additional information is sought after to debug and nail the issue. Tapas Sahoo has enumerated some basic validations that you (as a Coded UI Test user) can attempt to troubleshoot the problem. He also describes a few workarounds that you can try out for some common failure scenarios.
The full post is available here.