What does the rest of it say? It should say requires x but only y available.
Yes it will delete older backups but never the last one.
So it needs more than twice the space of what it is backing up.
The bold part is not entirely true. Time machine will only backup the files that have changed since the last backup, so you need a bare minimum backup drive equivalent to 1x "Used" source disk space + space of any files that have changed. It does this by creating hard links for files that have not changed, so there are multiple folders/files organized by date, but they all point to the same "data" on the disk (until the source file is changed).
To mdijb: More information about your drive setup would be helpful, how many, total size and used space and any files / drives in the TM "excluded" list. It's possible TM is trying to backup more than you think (like another external drive you attached), but no-one can say without more info.
MS