Time Machine Fails During Backup

So I did a search here and found various Time Machine issues, but not this one inparticular. Yesterday time machine was running and I got the following error:

"Time Machine hasn't backed up your computer in 116 days..."

I go to the Time Machine preferences and I click the little info "i" next to the "Failed" status, and it says "Back up is too large for disk...requires 21.92 GB, but only 21.85 are available."

I have a 500GB FW400 hard disk as my Time Machine, and I've never seen this error before. I figured since TM deleted old backups when the disk got glose to full, that this issue shouldn't happen. I just tried to run a back up again and I got the same errors. It gets to the "cleaning up" stage of the back up, then craps out. Any one have any clue what's going on?