I'm trying to use File History however I may not be fully understanding it or its requirements. My thought from the way it is setup is that it would make backups of changed files until the disk fills up and then would delete the oldest ones to insert the newest (if you configure it that way in the advanced settings). This would mean you could use it to backup say a 1TB to a 250GB drive, acknowledging that you would only retain a certain percentage of the files. This is how I have configured but File History consistently fails with a disk full error rather than re-using space on the disk. Is there a requirement that the disk used for File History must be at least the same size as the volume being backed up?

That should be how it works, yes. Are you sure the option says "until space is needed?" I see a lot of users that tried to select that, but didn't click "Save" at the bottom and didn't realize it.
Have you run checkdisk (chkdsk) on that drive?
Windows 8 - Improve performance by optimizing your hard drive - see "To repair a drive:

http://windows.microsoft.com/en-US/windows-8/improve-performance-optimizing-hard-drive

==============================
File History is an incremental backup method.
Note in Control Panel - File History - on left side Advanced settings - Size of online cache
- the maximum size is 20% of the drive/partition size.

How to use File History (Windows 8 & 8.1)
http://windows.microsoft.com/en-US/windows-8/how-use-file-history

What if something goes wrong in File History? (Windows 8 & 8.1) http://windows.microsoft.com/en-US/windows-8/what-something-goes-wrong-file-history

Setup a drive for File History (Windows 8 & 8.1) http://windows.microsoft.com/en-US/windows-8/set-drive-file-history

Protecting user files with File History (Windows 8 & 8.1) http://blogs.msdn.com/b/b8/archive/2012/07/10/protecting-user-files-with-file-history.aspx