Time Machine files cannot be erased
Deleting Time Machine backups can take a very long time, since they can contain hundreds of thousands of files. Moving the files to the trash can take a long time, emptying the trash can take a long time, and using command line "rm" commands can take a long time. By long time I mean tens of hours.

Usually the fasted way to remove such numbers of files is to use Disk Utility to erase and/or reformat and/or repartition the drive. Copy anything you don't want lost off of the drive, reformat it, and start the TM process again.