The factions against King Arthur? What? That doesn't service the story at all. Arthur is the one true king.
And it does have random quests! Expect more to come with updates!
I don't find the replayability limited at all. Four ways to play each very unique that demand different playstyles, in the quest adventures but also in the tactics you implement in your battles. In TW, it doesn't matter WHO you play because you'll be playing the same way. Your decisions will consist of the same train of though and your tactics won't vary much at all.
I've already spent 33 hours with this game. Left 4 Dead 2, which I got before this has been played only 35 hours. King Arthur will very soon overtake it and I think it very well may challenge my "always on" game of Football Manager which has only kept its lead at 50 hours of game time in the past two weeks.