Time Machine - preparing to copy "forever"

Problem:
I just got a new HD in my iMac (HD replacement action of Apple). Got the latest MacOSX on it. So far so good, but placing back my data from my Time Machine backup disk, I ran into problems. I had first a message and sometimes errors, telling that my disk was not properly removed (however, that was done by the OS itself). I just restarted the computer and tried it again. I started with an action to place back some data (couple of MB's), just to try if everything was working well.
Well, it didn't. It was preparing to copy forever. And finder hang, couldn't shutdown the computer on the normal way. So, just hard reset...
Solution:
Due to the 'not properly removed' messages and errors, I decided to run the Disk Utility and from there I ran the 'Verify Disk' option on my Time Machine (TM) backup disk. This took about half an hour or so. The results it shown were all good (green messages).
But, guess what, after that, restoring data from my TM Backup worked fine. Depending on the amount of data I restored, it took just a little moment to 'prepare to copy' and then it started to place the data back on my computer just as aspected and with an appropriate speed!