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.
This happened to me again recently, and just excluding folders from the backup wasn't enough, so I found another trick. Let's say you analyze your hard disk contents and realize there's a 20GB folder (let's call it UselessStuff) which was being backed up. You exclude it from the backup as described above, but that doesn't delete the previous backups of UselessStuff from the disk, and you still don't have enough space for the backup to complete. Since you don't need any backups of UselessStuff, you can enter Time Machine, right click on UselessStuff, and click "Delete all backups...". In my case, this freed up enough space to let the backup continue successfully.