I have had a similar problem but it appears all of my backups on the external HDD have been deleted.
I upgraded to Yosemite about 4 days ago, on an iMac.
I can enter TM and on the RHS it showed dates going back about 4 years. When the backup started it shows "Preparing Backup" then says backup failed because of not enough space. I had about 22gig left on a 500gig drive.
Problem is, it deleted all of the old backups and only shows the one in progress. I tried to "Delete all files in MOVIES" but nothing happened.
I know TM deletes old backups to make space, but if there is more than 500gig required which I suspect, then why would it not undelete the backups after figuring out there is not enough space available.
Am I now stuck with no backups whatsoever? Is this build in "enhancement"?