I found LOTR lacking storywise. It's a long episodic journey with lots of walking and periodic encounters with troubles. The actual plot lines aren't anything amazing and it lacked a lot of literary techniques, plus a deus ex machina type ending...the good guys won by a fluke. Plus the hero was the sidekick. Compare that to a Pixar like Monsters Inc or Incredibles, where you've got the plot twist, foreshadowing, nemesis character and climatic confrontation, and dialogue+events that further the main and sub-plots following the story arc, rather than be episodic and unrelated, and you see Pixar has buckets more story to it than LOTR.
But that's understandable. LOTR was never written by a guy wanting to create an amazing story. Tolkien was fascinated by mythology and wanted to create his own, so followed the principles of myth and fable in the creation of his ideas. He wrote the Hobbit for fun, and wrote the LOTR on the back of it's unexpected success (the Hobbit had buckets more story than LOTR). The fact LOTR was voted the best novel of the 20th century shows that story isn't everything. SOTC is a similar success. The story is, as I understand it, very simple - go kill things. It's in the execution and creation of a believable alternate world that it's appeal lies.
I think more often than not game to film conversions flunk because games are more about what you do than the storyline. The storyline is there to push it along, but the fun comes from the gameplay. Lose the gameplay and often the weakness of game stories shows through, including trying to turn the story into a 2 hour movie. Off the top of my head, Mario and Mortal Combat are classic examples where the games had no amazing story but were enjoyed for the gameplay, whereas the transistion to screen took characters desinged for games and tried to create a plit around them to dire consequences. Kameo presumably isn't a well developed character, so transplanting her into a movie and finding a story that's rich and involving could prove very difficult, depending on what the game story is like and how much scope for development the character has.