After a Time Machine restore, now it won't do incremental back up
Four options are available for you - none of them is a clear winner that works in all cases:


Try to force the issue with the command line tmutil inheritbackup command
Ditch the backup history and start over (not good, but quick)
Use a tool like BackupLoupe and see if you can thin space on the drive to make enough room for the "estimated" amount of storage for the next backup.
Baby sit the backup, by excluding most of the drive and unexcluding it in less than 250 GB chunks.


This last option has gotten me over the hump several times when clients cannot afford to lose their backup. I image their backup drive before starting (just in case) and then use the Time Machine System Preference options to exclude most of the drive. The first option is the most precise if you are comfortable with the terminal application and command line tools.



By excluding everything except perhaps /Library and /System you should be between 10 and 30 GB for the estimated size of a Full Backup and Time Machine will let you make a new backup. Then the trick is to slowly remove items from the exclusion list in stages to not have the next backup estimate exceed the remaining free space on your backup volume.