This is very interesting. I've had my MacBook Pro running Snow Leopard since January 2011 and Time Machine has never worked properly. TM arbitrarily decided to stop incrementing and start adding brand new backups to the sparsebundle until the 1Tb TC was full. I'd have to delete the sparsebundle and begin again. We tried erasing the TC completely with no improvement. We tried verifying and rebuilding permissions, and a soft reinstall of Snow Leopard, no change.
I was finally advised by Applecare to drag and drop my data files to the TC as a backup, and get my MacBook Pro disk wiped and reinstalled with Lion, which I did last week. I made a backup of the clean install and copied it to our NAS. The data files have now been copied back, and TM restarted and by day 2, I got the "to improve reliability Time Machine must create a new backup for you" message, and bingo, I'm back to square 1 again - no reliable backup.
The most irritating part is that my husband's (mostly wireless) backups from his elderly MacBook running Leopard onto the same TC have been working perfectly since 2009. I have a new MacBook Pro, using a Cat 6 ethernet cable on a 1Gb network, running a fresh install of Lion and it doesn't work. The hours I've wasted on this.
Pondini - thank you for your articles. I've bookmarked them and will work my way through to see if there's anything I've missed. I'm starting to suspect everything from the concrete walls to interference from the Sky receiver, the electric kettle or passing aircraft 30,000 feet up...