Mavericks setup fails: "the recovery system can't be created"

I've been trying to upgrade from OS X Mountain Lion to OS X Mavericks, but the setup fails after a few minutes with the message that it can not create the recovery system. The relevant installer log items are listed here:

Oct 24 11:47:44 192.168.2.1 OSInstaller[379]: Recovery system creation failed with error -69866 (Couldn't complete copy)
Oct 24 11:47:45 192.168.2.1 OSInstaller[379]: Install failed: OS X can’t be installed on the disk Athena, because a recovery system can’t be created. Visit www.apple.com/support/no-recovery to learn more.
Oct 24 11:47:46 192.168.2.1 OSInstaller[379]: Reverted bless to disk Athena

The complete log is uploaded as a Gist.

When I try to boot in to the existing Recovery environment, by holding Cmd+R on boot, I get booted in to the Internet Recovery. Also, I have checked if the Recovery partition is missing, which it isn't. This is the output of diskutil list:

/dev/disk0
  #:                       TYPE NAME                    SIZE       IDENTIFIER
  0:      GUID_partition_scheme                        *121.3 GB   disk0
  1:                        EFI                         209.7 MB   disk0s1
  2:                  Apple_HFS Athena                  119.5 GB   disk0s2
  3:                 Apple_Boot Recovery HD             650.0 MB   disk0s3

When holding Opt at boot, the Recovery HD does not appear as an option.

What can I do to fix this problem and to upgrade to Mavericks? Thanks!

Apple recommends that you backup, erase and reinstall the original OS X, then try updating again, as per the instructions below. However, it is feasible to merge steps 3 and 4, installing Mavericks in step 3, then restoring your data to that OS.

1. Make a full backup of your hard disk and all of its data (including your Boot Camp partition, which is not normally backed up by Time Machine).
2. Erase your hard disk and create a single Mac OS Extended (Journaled) partition.
3. Reinstall your original copy of OS X.
4. Re-download the OS X upgrade from the Mac App Store and retry your upgrade install.

^{Source: Apple KB Article HT4649}

Alternatively, you could use an app such as iPartition to delete the Recovery HD then extend the startup disk to fill the free space. Since there is now no Recovery HD, the installer should have no problem creating one from scratch.