This happened to me recently; I was pretty annoyed because I expected that if there wasn't enough space, Time Machine should just delete the oldest backup.
The problem turned out to be that the disk contained only one (large) backup, and didn't have room to store the current delta (delta = changes to files since last backup).
I realized this when I looked at the disk contents and saw that there was only one backup folder under Backups.backupdb.
I used Disk Inventory X to look at the contents of my hard disk, and identified a few large folders which didn't need to be backed up. I excluded these from the backup using "Time Machine" > "Options" > "Exclude these items from backups". The info from Disk Inventory X also led me to delete a bunch of large unused files.
After the two changes listed above, the backup proceeded successfully. I didn't have to launch the backup, it automatically retried. I presume that my changes brought the delta to a small enough size that it fit in the remaining free space on the backup disk.