Neil Gaiman has written some absolutely shattering graphic novels (Sandman), some pretty good books (American Gods), and some films that while innovative rarely achieve the same level of shock and awe (Mirror Mask). Part of this is because Gaiman's strength is in complex interwoven storylines where characterization is set in context with a much larger situation. Part of this is because where Gaiman really excels is the creation of new, iconic, mythologies with recognizable literary underpinnings. When he does this correctly, his gods, demons, and backdrops are resonant.
But this is hard to do in a 2hr movie.
Stardust is based on about 10.5 hours of material in the original 1998 graphic novel by the same name (and the same author). It's a fairy-tale set about 150 years ago where a young man journeys through a hole in a wall (in the town of Wall) that separates our world from a magical one. He's going to find a fallen star and return it to his beloved so he can win her hand in marriage--she doesn't really respect him that much (he's a shop-boy) and is dating one of those arrogant good-at-everything jerks that appear pretty often in cinema ... and for a specific reason.
And, of course, on the other side of the wall, is a cross-fire of magical intrigue around princes and witches who want the star for themselves.
The star is played by Claire Danes, who has been knocked from the heavens by accident and now can't get back ... without help (and certainly does not want to be the captive prize of a love-struck shop boy). Adventure ensues.
So, is it a good adventure? Yes: it is a pretty darn good adventure.
Gaiman knows how to work a fantasy world with an internal logic and this carries through into the shorter, tighter movie script. The original books were quite dark (and had mature themes) but the film is a good deal lighter (it was compared, reasonably, to the Princess Bride--although without the humor focus). There are witch-battles, princes killing each other off, ghosts, and sky-pirates with a flying blimp / sailing ship who bottle lightning and are run by Robert De Niro.
The screenwriters (Jane Goldman and director Matthew Vaughn) give us a steady build-up with satisfying set-pieces and drama in an arc that takes us exactly where we think it's going to go. The acting is good. The F/x are good. Claire is pleasant to look at and everything falls into place.
If I have a complaint, it's that: the show clocks in at a somewhat edgy PG-13 but doesn't really challenge us. There is a mechanical injection of "the stupid" where two major characters simply must misunderstand each other in order to feel betrayed (fortunately the movie doesn't linger here). There is an ending sequence that absolutely floored me until they took it back (a main character decides things didn't really need a final, climactic battle ... then, oh wait, yes they do).
This is all the more noteworthy because there are places in the movie where it does give us pause. The pirate captain (Shakespeare) turns out to have several layers of secrets that "had better not come out"--and do. The scene where the boy returns to the human side of the wall avoids complete cliche. There are glimpses of what might've happened with another hour and an R rating (or, maybe, Terry Gilliam at the helm--he was picked for it first but begged off due to being sated with fairy tales after The Brothers Grimm ... maybe this is a good thing, considering how The Brothers Grimm came out).
If the movie had really cut loose and given us material that ran counter to the way most western movies are made (and I don't mean a "bad ending" but more about structure with anti-climax and such) I think I might have come away with it awestruck ... or maybe star-struck. But as it is, while I recommend it as a clever movie, I'm not blown away enough to give it an 'A.'