See, I said this would happen didn't I.
I managed to break every element of Windows and now I'm even managing the same with MAC OS X!
This one got me for a while though, basically I found that my 500GB External Passport Drive was full, it made sense because the day prior I moved 200GB of data from one location to another, so I guess the time machine simply presumed it would backup the same data but in different locations hence running my drive out of space.
The issue was that Lion (to my understanding) would delete old backups in order to fix the space issues on my drive, apparently this seems like it isn't quite accurate. You have to go into Time Machine and Delete the old files you don't want anymore. So here's how I did it, I spent ages in that stupid Time Capsule Preferences window with barely any settings to change and just shy of chucking the machine through the window i noticed that in the top right where you locate the Time Capsule icon you can actually hit Enter Time Machine which takes you into the Backup Program. Now if you navigate to a point in time or to a set of files that you perhaps don't need anymore. Right click and hit delete all backups of... This will clear out your old data on the backups and allow the program to continue.
Obviously this won't apply to everyone, 50% of you will probably actually have a full disk. In which case, go out and buy another! The remainder however; this should help you out hopefully.
Hope it helps :)
Did I solve your problem? Buy me a virtual beer by clicking on a Google ad :). Thanks!