Try opening the "Spotlight" system preferences and try adding the new Time Machine drive to the "Privacy" list (drag it there), which will prevent it from being indexed. Then try backing up again to see if this allows it to complete the backup.
Also try using the Disk Utility program to run a verification routine on your boot drive to see if its formatting is healthy.
Time Machine will just, sometimes, crap out - particularly with a new backup. If I were you, I'd just try reformatting the drive and starting the TM backup anew - no use waiting, just force quit the backup.
For everything you'd ever need to know about Time Machine, see http://www.pondini.org/OSX/Home.html.
I finally took my computer and extrnal HD's to the Apple store. The genius said I was trying to force too much data through a USB 2.0 connection which was hanging it up. He suggested consolidating my external hardrives into one with two firewire 800 connections and daisy chain that to my Time Machine Hard Drive. It now works perfectly.