Time Machine Will Not Regularly Back Up

Hi,

I've been having a problem recently where I can create an initial backup for time machine, but after that it will not regularly back up. If I try to manually "back up now", it will try to create a whole NEW file, instead of updating the pre-existing one, and then of course it says there isn't enough room to back up. In essence, it is not recognizing the pre-existing backup as being the same computer, I don't think. This is the message I get when it tries to back up each hour:

"This backup is too large for the backup disk. The backup requires 70.56 GB but only 24.82 GB are available. Time machine needs work space on the backup disk, in addition to the space required to store backups. Open Time Machine preferences to select a larger backup disk or make the backup smaller by excluding files"

I can go into Disk Utility and erase the data on the partition of the back up hard drive and then create a whole new backup, and I have been doing that for a few months, but as you might imagine this is time consuming and not nearly as convenient as letting it back up on it's own every hour.

My logic board has not been changed, as this thread deals with:

http://forums.macrumors.com/showthread.php?t=391208

Does anyone know what might be going on? I use a Western Digital backup hard drive and back up wirelessly through the Apple Airport Extreme. I'm running Snow Leopard. I appreciate any advice anyone might have!

 

There are three partitions for the drive, but each is used for TM. We have two iMacs and a Macbook in our household. One iMac running Leopard backs up just fine, but the Macbook running Snow Leopard has the same problem as the iMac that can't back up regularly.