The system over estimates the amount of space needed when large changes are detected (say if an entire folder changed in a way that it can't easily tell the files inside are the same). Also, minor file system corruption can wreak havoc on the algorithms. Have you rebooted the mac in safe mode to force a fsck file system check to rule out that error?
That will usually force a full filesystem traversal and may let the system go back to not over-estimating the space needed by such a large amount.
With Lion - you have the excellent tmutil
command. You could turn off automatic backups and use the tmutil compare
command to see what has changed since the last backup. It's a very powerful tool and you can get a much better feel for what has changed - either between specific instances in time or overall.
Furthermore, to get out of the situation, you can often "nurse" the backupd process along by adding most of the large folders on the drive to the Time Machine exclusion list. Most of the time, adding /Users and /Library is enough. You can also let Time Machine skip backing up the system and try that to get a partial backup. By not changing files and letting it process parts of the drive and not assuming that it needs to do the entire drive in one hit lets you relax the exclusions list progressively until the whole drive is again backing up without complaint.
fsck
file system check to rule out that error?