My MacBook Pro Core 2 Duo 2.2GHz has a 120GB hard drive, and I am using about 62GB of space. I am also using VMware Fusion with two virtual machines (one for XP and one for Vista) that totals about 18.9GB. In Time Machine's system preference's panel I've set the do not backup option to not backup the Virtual Machine folder. Time Machine says that the total includes 44.0GB, so I connect my external drive, and begin to backup and Time Machine says that its copying over 62GB of data. So I stop the backup, then I go back to the system preference's panel and I click on the virtual machine images themselves (not just the virtual machines folder). Then I tell time machine to backup, and guess what...it still says that is copying over 62GB of data...arggg!
Here's a video I made about my Time Machine issues.