So, my 2TB Time Capsule says that the backup disk is full, even though both the TC preferences and the airport utility says that it has 1.74TB free. If I open the sparse bundle, I can see backups back to June 2016.
The warning is telling you TM will delete older backups, not necessarily that the disk is full (although it says that). It may be the backup has become corrupt.
If your Mac is in a good state, you could delete the old backup and start a new one.
It ended up that there was an external drive plugged in, and it was full. Once I ejected that one, everything returned to normal, with my backups going back a little over a year ago.