Re: Stats
Derulbaskul said:
Don't forget that he also uses a kama and throwing stars. You may also want to give him a level or two in ranger (or more), particularly as he fights two-handed. Adding to the ranger argument are his wilderness lore and animal empathy: the former because he knew the sandstorm was coming and how to deal with it, the latter in terms of his obvious deep respectful love and affection for his, um, camel. 
I would also argue that he was probably using a monkey gripped falchion (dumb name- why not iron grip instead?) rather than a scimitar. Then again, I'm no expert of ancient/medieval weapons.
Cheers
NPP
Good point, you forgot some stuff that I did. So, I quickly updated the stats. I gave Mathius two levels in Ranger and one more level in fighter. I picked animals as his favored enemy, even though humans would have been more accurate, but the 'evil' barrier got in the way again.
Mathius
Male human Ftr8/Rog3/Rgr2: CR 13; Medium-sized humanoid (human); HD 7d10+28 plus 3d6+12 plus 2d10+8; hp 113; Init +3; Spd 30 ft.; AC 15 (touch 13, flat-footed 12); Atk +15/+10/+5 melee (1d6+8/18-20, scimitar) or +14/+9/+4 ranged (1d8+6/X3, mighty composite longbow +4); SA Fight with two weapons, Sneak Attack 2d6; SQ Evasion, Uncanny Dodge (dex bonus to AC), traps, favored enemy (animals +1); AL N, SV Fort +13, Ref +8, Will +3; Str 18, Dex 16, Con 18, Int 11, Wis 11, Cha 17. Height 6 ft. 5 in.
Skills and Feats: Animal Empathy +2, Climb +11, Disguise +4, Handle Animal +5, Hide +6, Intimidate +4, Jump +5, Move Silently +5, Ride +7, Search +1, Spot +3, Swim +5, Use Rope +4, Wilderness Lore +3; Cleave, Combat Reflexes, Exotic Weapon Proficency (kama), Exotic Weapon Proficency (Shuriken), Improved Unarmed Strike, Point Blank Shot, Power Attack, Track, Weapon Focus (Mighty Composite Longbow +4), Weapon Focus (Scimitar), Weapon Specialization (Mighty Composite Longbow +4), Weapon Specialization (Scimitar).
Possessions: Scimitar, Mighty Composite Longbow +4, leather armor, several daggers and other assasination tools (kamas, shurikens, etc).
Now, as for the other characters in the movie:
Memnon, the villian, would be a high-level fighter with improved two-weapon fighting and arrow deflection.
Cassandra, the sorceress, is a diviner if I've ever seen one. I might give her a level in fighter, since she seemed to be able to handle a sword pretty well.
Balthazar, the tribal chieftan, would be a barbarian with a
very high strength score.
