Had my iMac 2009 21.5" hard drive replaced a few days ago, from a 500GB to a 1TB. This was done by an authorized Apple repair dealer. I have been trying to run backups through Time Capsule but it seems to be getting hung up at one stage or another. Why is my Time Capsule backup getting stuck on "preparing backup" or "cleaning old backups?" The new hard drive has caused a huge positive difference in performance, which is suffering as the Time Capsule and backups get "hung."
tmutil status for a much clearer idea of what's actually happening. Keep running the command and the NumberOfChangedItems should be changing if the backup is taking place. Until then, the command will inform you what's being processed.