No no no people. You don't just think up popular actors for movies like this, you cast for unknowns. Seriously, the best way for a movie like king's quest would be unknowns.
Graham would be an unknown DEFINATELY, it would be a joke to have any of the actors mentioned for him in that little hat of his.
Rosella I think could possibly be a popular actor but she needs to look more European. Not any of these pretty american girls. Actually, a Norweigan actress would work really well.
Valanice- Italian lady. Kind of like Kelly McGillis:
http://www.peterweircave.com/witness/km.jpgShe's gotten older since Witness but Valanice isn't exactly young.
Alexander- Any number of guys could go for this Heath Ledger actually sounds pretty good although I think his face structure isn't ideal for the character. Orlando Bloom is a no no. Not only does he not look anything like Alexander but also I can't stand his acting. He conveys emotions generically and delivers them in such a insignificant way. As far as innovativness goes, he's nothing special.
Another possible famous actor for Alex is possibly Joseph Fiennes but he might be a tiny bit too old.
Director- TERRY GILLIAM! Best choice all around. His quirky touch to this would be perfect. The way he uses old methods instead of CG all the time for his special effects transports like no other director. If you've seen Brothers Grimm you know what I'm talking about.