Chris Pirillo forwards a fairly nasty sounding Time Machine bug (OS X):

After exhausting my search of Apple’s support page and trying a few things. I resorted to calling Applecare for assistance. After about 45 minutes of troubleshooting and talking to other reps, my rep came back as dumbfounded as I was. I was told that instead of deleting older backups, as advertised, Time Machine instead begins compressing the older ones. If you run out of space before the compression can catch up, Time Machine will fail, as it does not have enough space to create a new backup directory. The only way to restore functionality is to completely erase your backup drive and start from scratch.

I think I'd do what Pirillo suggests in his comments - archive the drive and buy a new one. Or maybe try and manually blow away the oldest stuff. Either way, something to watch out for

Technorati Tags: Time Machine, backups