Time Machine backup is too large (but shouldn't be) I get:

This backup is too large for the backup disk. The backup requires 35.72 GB but only 24.79 GB are available.

Facts:

Estimated size of full backup: 149 GB

Size of Backups.backupdb on the Time Machine drive is 166 GB and there is 18GB of free space on the drive.

So why doesn't the backup go through? It should be able to delete old files... especially since the current backup size on the drive is less than it is required for the new one.
I know what is the problem... I only have one backup on time machine and it won't delete it because it's the only one. So I can either clean up some space on the drive (I have other things there) or just delete the backup and let it run again.

How to delete a backup - from here:

The easiest way is to:


Enter time machine (on the Mac whose backup you want to delete)
Go to the point in time you want to delete
Select the icon that looks like a cog in the finder and choose 'Delete Backup'
This ensures the backup catalog remains accurate and the integrity of your data stays intact.