Solution 1:

You do not have to just wait, you can see what is it doing.

From the Mac App Store, click on the “Purchases” tab to see the active list
Locate the app(s) you are downloading that you want to check

This will show you the download progress bar, the total downloaded out of the total download size, and an estimation of time remaining until the app has completed downloading and is ready for use.

Meanwhile you can clean the temporary download:

Run this command on the terminal: open $TMPDIR../C/ ...

It will open up Finder in a specific folder, you select com.apple.appstore and delete this folder.

Solution 2:

Cancel the download if it is showing up in your Purchases tab. Then open Finder and go to Application and make sure that OS X Yosemite Install is not there, if it is, drag it to the trash to delete it.

Restart your computer and instead of downloading it from Purchases navigate to it in the App Store and download it from there.

If THAT fails. Call Apple and tell them you are having issues. Sometimes your download queue can get stuck and they can manually clear the queue out to download it again.

Solution 3:

For anyone else encountering this issue when upgrading to Yosemite, the way I eventually got past it was simply to reinstall Mavericks, and then to upgrade to Yosemite.

Worked like a charm, after trying various things like clearing cache, flushing DNS, running in safe mode etc without success.

This solution was recommended to me by Apple Tech Support (after first suggesting verifying the disk from Recovery Mode and trying the upgrade from a freshly created admin account). You won't lose any personal data reinstalling Mavericks.

(For me this problem manifested itself as: the full 5.6Gb package would download, and then fail almost immediately with a totally uninformative "PKIInstallError" code of 112 in appstore.log.)