Glad this solved your issue too. This only happened on one of my macs, so it may not occur every time someone upgraded from Lion to ML to Mavericks, but I read a few posts where people were in the same position. I wanted to upgrade rather than clean install or formatting since I have loads of apps and config and didn't want to risk losing them (many not available on app store!).
Ok here were the steps I followed (some of which I obtained from various other people on the web who I would like to thank!):
1. When originally trying to upgrade to Mavericks on my MBP using the App Store download I got the error "the recovery system cannot be created. The system rebooted and went back to Mountain Lion.
2. I connnected my MBP to another mac in target disk mode (using Thunderbolt) - holding down 'T' on startup
3. I opened disk utility and created a backup disk image of the whole Mountain Lion drive on my MBP (which includes the Mountain Lion Recovery Partition).
4. I mounted the backup image and verified using the terminal that it indeed contained the recovery partition in case anything went wrong (using the command 'diskutil list')
5. I opened iPartition to delete the recovery partition on the MBP and extend the 'Macintosh HD' partition to use up the extra space (this should not delete any data, but I didn't trust this, hence the backup I created!).
6. I then disconnected the MBP and restarted it. I opened terminal and checked 'diskutil list' again and verified the recovery partition was indeed gone.
7. Then I tried to upgrade to Mavericks again. This time it worked, and the installer created a new Mavericks partition, which I verified after upgrading
Hope this helps!