Hi,
I have found that recording tests using IE is problematic.
First of all the other browsers seem to name map differently to IE and so often will not work on playback. Interestingly however, is that If you use, for example, Chrome to record your tests then they *should* also work on IE and the other browsers (just not the other way round).
Using a different browser to record your tests may magically fix your problem.
One other thing I'd like to mention is try to map your most used objects using the "Map object from screen" before recording your tests and if possible/needed change the names to something more sensible. This should help you when you come to debug your tests as well as make it a little more readable.
Hope this helps.