I'd have to agree that constructed names like Shadowheart appeal more to me than a lot of purely made-up names; it's the way many place names, geographic feature names, and family names have come about, so it's easy to relate to.
I often find that a body of entirely fictional names have a randomness that makes them difficult to process and remember. To create a credible body of fictional names it helps to build up a fictional language first, as with Tolkein, and that is beyond the skills of some authors.
