Time Machine error creating the backup folder on a spacious hard drive
I had the exact same symptoms with a Nov 2013 MacBook Pro (came with Mavericks already installed) using WD "My Passport" USB drives for Time Machine backups.  The solution was to erase and reformat the external drives using Disk Utility as described in
   http://support.apple.com/kb/HT5911 under the heading "Erase and reformat the storage device".

I had a spare drive so, in order not to lose existing backups, I did the following:


erase spare drive as above
use Disk Utility to "restore" the backup drive's volume to the erased drive
(you have selected the volume correctly (rather than the drive) if the Disk 
Utility window shows 
    "First Aid; Erase; RAID; restore" as options
not 
    "First Aid; Erase; Partition; RAID; restore")


After this I have no problem doing multiple backups in a row, putting the machine to sleep without ejecting the backup disk and then doing a further backup, and no problems with ejecting the disk.

Good luck!