In theory, Time Machine is supposed to delete the oldest backups automatically to make room for new backups, but as you......and countless other users have found.......the theory does not work in practice.
The fact that you are seeing a message that there is not enough room for a new backup confirms that Time Machine cannot do for you what it claims to be able to do.
The simplest, quickest, and most reliable thing to do is simply erase the Time Capsule hard drive and start over again with a new backup and move forward from there.
Few of us ever need the old backups from weeks, months, even years going back, but some users have a tough time erasing them, even though they will never need them.If you cannot bear to lose the old backups, Apple provides a means for you to Archive or copy all of the data on the existing Time Capsule hard drive over to a USB drive before you erase the Time Capsule drive.
Let us know which route that you want to take and whether or not you need a few more tips to get the process underway.