I work at a center that handles AppleCare and I'm specific to the Mac OS X Advisor team. Based on what you've told us, I think visiting an Apple Retail Store would be your best bet. Take it in and have somebody look at it. If you can't get it to verify/repair the disk, there's likely a problem with the HDD. It might come down to getting a new one installed and seeing what can be salvaged from that old one.
It sounds like you've done everything we'd go through with you over the phone, but if you want to call AppleCare and double-check, ask for a Senior Advisor/Supervisor as the initial Advisor will likely take you through the steps you've already gone through. And if you're worried about being charged for the call, everyone who installed Mavericks gets 90 days of free phone support, so take advantage of that.
Just have your serial number handy if at all possible and remember to be kind to your phone tech as they'll really appreciate it! I know I always do.

Good luck!