Hi dj,
This can happen if you do not restore your tested application back to its initial state after recording the test. Without that done, any data entered during the test recording still exists in the application, so the application prevents from entering the same data during the test run. I'd like to emphasize that in this case, the error is shown by the tested application, not by TestComplete, so it's not a TestComplete issue.
To resolve the problem, you need to reset your application to the initial state before running the test. For example, roll back its database, remove any data files created during the test recording, and so on. Try doing this and let me know whether this helps.