Like Castlevania or Zelda, Metal Gear might appear at first glance to be a generic movie stuck in the cliches of its genre...until five minutes into the military espionage they that Snake's up against a telepath, a shape shifter, a cowboy, a cyborg ninja, and a bipedal tank.
Of course, the biggest problem would be fitting the script into the time frame for a movie, which I'm not confident that they'd do well. Just watch most book-to-movie transitions...they cut out stuff that, in the long run, creates nothing but plot holes when it turns out they made a big mistake. A bigger risk than the others, but certainly not impossible. Besides, the Codec calls need to be trimmed down anyway.
The real appeal to these hypothetical great video game movies is the settings, not just the plot. Dracula's castle, the Kingdom of Hyrule, the Mushroom and Koopa Kingdoms (and any setting in between), and the paranormal military bases are all interesting enough to work into a movie without having to rely completely on the existing scripts.
Are there pleanty of Eastern story driven games that are just as stereotypical as westerns? Sure. A common target is Final Fantasy VIII--brooding teen lead who charges gun-wielding foes with his over-sized sword. However, the game also features flying military schools, a time-controlling sorcerous, summonable monsters with amazing power, and an invisible, technologically advanced city in the middle of all this. The story itself is founded on stereotypical characters, but the setting is interesting enough to potentially make up for it. Maybe that's what Bob meant with the "for a Western game" comment. A western gaming with a less-than-great story doesn't often have the setting to back it up.