the first backup usually takes forever and is best left to its own devices.
Just leave it running and you will probably find that it will, eventually, get itself sorted out.
I've just bought a new iMac and I've moved my two external HDs from the old Mac to the new. I've designated a 1TB HD as my Time Machine disk and started a new back-up of 92 GB (excluding all external HDs, System files, etc). The HD is mains-powered and has a USB2 connection.
The back-up ran - it took 8 hours and then stalled for over two hours at the "Cleaning Up" stage, so I just restarted the Mac and erased the HD.
I've repeated the process and the message of time to go varies from 6 to 7 hours.
This never happened on the old Mac - a new back-up took only an hour or two.
Is something wrong?