Time Machine fail

I have a 2Tb FW800 Western Digital drive for Time Machine. It's starting to get full and so I expected TM to wipe the oldest backups automatically.

However, I get nothing but fails.
Tried to verify my internal HD (only disk being backed up).
Looked here :
http://pondini.org/TM/C18.html

Strangely, during the backup, it says for example 'backing up 14,9 Gb of 20,1Gb' but the 20,1Gb keeps increasing as well.

I verified and repaired my internal HD, rebooted, but to no avail.
I'm running OS X.8.4 on a mid 2011 iMac.

Any suggestions ?