Time Machine is attempting to backup 500GB of data, and there's only 250GB available on your external hard drive. You either have a really big internal drive, or Time Machine is trying to backup itself.
Go to System Preferences > Time Machine > Options. Make sure that it's not trying to backup the same disk that it's using for backups.