I have the exact same problem with almost the same setup: MacBook Pro (Retina, 13-inch, Late 2012) running Yosemite 10.10, an external harddrive and a Time Capsule 2 TB (4th Generation, Version 7.6.4). I even took the same actions as geoff2 (deleting the complete set of backups from Mavericks and making a new complete backup on Yosemite). On my internal harddrive 270 GB are occupied, on my external harddrive around 980 GB are occupied and the MacBook of my girlfriend is also backed up to the Time Capsule. At the moment around 646 GB are available on the Time Capsule.
Now I get the same error message saying, that 977 GB are needed for a backup but only 650 GB are available. Interestingly backups without the external drive connected will complete without any problems.
The external drive has a "GUID Partition Table". So it seems both of Linc Davis suggestions don't apply to the problem (we both have either GUID Partition Table or Logical Volume Group and the issue appears both on a NAS-Storage and on a Time Capsule).
Looking for additional information I looked into the console and found the following report: "Inheritance scan may be required for '/Volumes/Dolphin', associated with previous UUID: BA36E38E-71F9-39E1-BF72-36AF9D4BB45F". "Dolphin" is the name of the external drive. What does that mean? Is it of any relevance? For more information I will post all the reports concerning the backup below (it's mainly about trying to free more space on the TC by deleting old backups). "Yosemite" is my internal OS X Volume, "Hamster" is the name of the Volume on the TC, "Nifty" is a Nifty mini drive in the SD-Card-Slot.
I already verified the backups using the Option-Click on the menu bar symbol and I deleted and rebuilt the Spotlight index but it changed nothing. We could of course delete the backup volume (NAS or TC) and start a new backup, but I have a feeling, that the issue will appear again afterwards. Any other suggestions?
08.11.14 16:46:06,033 com.apple.backupd[4227]: Starting manual backup
08.11.14 16:46:06,071 com.apple.backupd[4227]: Network destination already mounted at: /Volumes/Hamster
08.11.14 16:46:11,000 kernel[0]: hfs: mounted Time Machine-Backups on device disk6s2
08.11.14 16:46:13,146 com.apple.backupd[4227]: Disk image /Volumes/Hamster/Nikos MacBook Pro 13" (2).sparsebundle mounted at: /Volumes/Time Machine-Backups
08.11.14 16:46:14,908 com.apple.backupd[4227]: Backing up to /dev/disk6s2: /Volumes/Time Machine-Backups/Backups.backupdb
08.11.14 16:46:19,914 com.apple.backupd[4227]: Inheritance scan may be required for '/Volumes/Dolphin', associated with previous UUID: BA36E38E-71F9-39E1-BF72-36AF9D4BB45F
08.11.14 16:46:27,375 com.apple.backupd[4227]: Will copy (10 MB) from Yosemite
08.11.14 16:46:32,745 com.apple.backupd[4227]: Will copy (0 KB) from Dolphin
08.11.14 16:46:32,748 com.apple.backupd[4227]: Will copy (0 KB) from Nifty
08.11.14 16:46:32,749 com.apple.backupd[4227]: Found 137158 files (954.27 GB) needing backup
08.11.14 16:46:32,752 com.apple.backupd[4227]: 977.06 GB required (including padding), 646.65 GB available
08.11.14 16:46:32,765 com.apple.backupd[4227]: Deleted backup /Volumes/Time Machine-Backups/Backups.backupdb/Nikos MacBook Pro 13" (2)/2014-11-08-164619.inProgress/B65EE357-083D-4E0B-900B-42910289B9C4 containing 4 KB; 646.65 GB now available, 977.06 GB required
08.11.14 16:46:32,767 com.apple.backupd[4227]: Removed 1 expired backups so far, more space is needed - deleting oldest backups to make room
08.11.14 16:49:20,472 com.apple.backupd[4227]: Deleted backup /Volumes/Time Machine-Backups/Backups.backupdb/Nikos MacBook Pro 13" (2)/2014-11-07-111400 containing 627.9 MB; 647.28 GB now available, 977.06 GB required
08.11.14 16:49:20,472 com.apple.backupd[4227]: Removed 2 expired backups so far, more space is needed - deleting oldest backups to make room
08.11.14 16:50:12,817 com.apple.backupd[4227]: Deleted backup /Volumes/Time Machine-Backups/Backups.backupdb/Nikos MacBook Pro 13" (2)/2014-11-07-171215 containing 59.4 MB; 647.34 GB now available, 977.06 GB required
08.11.14 16:50:12,818 com.apple.backupd[4227]: Removed 3 expired backups so far, more space is needed - deleting oldest backups to make room
08.11.14 16:50:48,156 com.apple.backupd[4227]: Deleted backup /Volumes/Time Machine-Backups/Backups.backupdb/Nikos MacBook Pro 13" (2)/2014-11-07-183323 containing 42.4 MB; 647.38 GB now available, 977.06 GB required
08.11.14 16:50:48,156 com.apple.backupd[4227]: Removed 4 expired backups so far, more space is needed - deleting oldest backups to make room
08.11.14 16:51:07,147 com.apple.backupd[4227]: Deleted backup /Volumes/Time Machine-Backups/Backups.backupdb/Nikos MacBook Pro 13" (2)/2014-11-08-112446 containing 25.3 MB; 647.41 GB now available, 977.06 GB required
08.11.14 16:51:07,147 com.apple.backupd[4227]: Removed 5 expired backups so far, more space is needed - deleting oldest backups to make room
08.11.14 16:51:28,134 com.apple.backupd[4227]: Deleted backup /Volumes/Time Machine-Backups/Backups.backupdb/Nikos MacBook Pro 13" (2)/2014-11-08-132002 containing 11.5 MB; 647.42 GB now available, 977.06 GB required
08.11.14 16:51:28,134 com.apple.backupd[4227]: Removed 6 expired backups so far, more space is needed - deleting oldest backups to make room
08.11.14 16:51:28,135 com.apple.backupd[4227]: Deleted 6 backups containing 766.6 MB total; 647.42 GB now available, 977.06 GB required
08.11.14 16:51:28,136 com.apple.backupd[4227]: Backup date range was shortened: oldest backup is now Nov 8, 2014
08.11.14 16:51:29,353 com.apple.backupd[4227]: Backup failed with error 7: Not enough available disk space on the target volume.
08.11.14 16:51:36,000 kernel[0]: hfs: unmount initiated on Time Machine-Backups on device disk6s2
08.11.14 16:51:37,508 com.apple.backupd[4227]: Ejected Time Machine disk image: /Volumes/Hamster/Nikos MacBook Pro 13" (2).sparsebundle
08.11.14 16:51:38,227 com.apple.backupd[4227]: Ejected Time Machine network volume.
08.11.14 16:53:43,804 SystemUIServer[431]: Attempt to use XPC with a MachService that has HideUntilCheckIn set. This will result in unpredictable behavior: com.apple.backupd.status.xpc
08.11.14 16:53:43,806 com.apple.prefs.backup.remoteservice[529]: Attempt to use XPC with a MachService that has HideUntilCheckIn set. This will result in unpredictable behavior: com.apple.backupd.status.xpc