John Carter sends this info, "I recently experienced that Time Machine on my computer would not delete an older backup to make room for a newer backup, and consequently the backups continued to fail with a message that there wasn't enough room for the new backup. I talked at length with Apple Support about this and we came up with no solution. I simply purchased a much larger backup drive and started over again. It may take months now before the new drive gets full.
"What I suspect was the problem was that my computer needs a backup drive that is more than twice as large as the total space USED in my computer. Since I'm using a little over 1TB that I want to back up, my new 3TB backup drive should now be more than adequate to handle two complete backups plus any additional incremental backups."