The next time you run a Time Machine backup have Console open. (Applications/Utilities/Console.app) It'd be helpful if you can post what error backupd (Time Machine) spits out under All Messages.
I've had similar errors with deep node traversal and I resolved them with Repairing the Disk via Disk Utility. Be patient though it takes a long time to repair.