After restoring from a Time Machine backup, I ran into this error when Time Machine then tried to create a new backup:
The backup is too large for the backup volume. xxGB is required but only yyGB is available.This occurs because Time Machine sees your restored computer as a completely new set of data and is trying to do a full back up. To solve this issue, open the backup drive that Time Machine backs up to, and locate the following file:
computername_0022334455.sparsebundleWhere computername is your computer's name, and 0022334455 is your computer's MAC address. Delete this file and have Time Machine do a new full backup of your system, and this error will disappear.
Mac OS X Hints
http://hints.macworld.com/article.php?story=2009102119415281