We just watched “Der Sternwanderer” (Stardust, by Neil Gaiman). I absolutely love this movie – what a wonderful fairy tale with great characters, nice twists and turns. I fail to see the issues some critics had about the movie and being able to follow the story. My recommendation: Watch it, enjoy it and take it as what it is – a simple yet moving fairy tale about all the strong motives of classic fairy tales: great evil meeting bravery in the face of at first unsurmountable adversity, true love and the strength of innocence.
BTW, I recommend everything from Neil Gaiman, his Sandman comics probably being one of the most powerful pieces of fantastic literature I ever read (yeah, literature in a comic series – can you believe that? The critics had some problems with that [initially]).