I consistently have the same issue with Legendary Heroes, though not with any other games on Steam.

Go into your Steam folder and rename your ClientRegistry.blob file ClientRegistryold.blob.  This will force Steam to download a new ClientRegistry.blob file, and will hopefully fix the problem.

Wonder if this fix in today's steam update will help:

Fixed failing to update a game properly if an unexpected folder exists in the install directory for a game and we want to replace it with a new file