@Campaigner: First of all, I would like to congratulate you for not judging games completely from the graphics. However, I would also like to "flame" you for judging games mostly because of their graphics.
I have plenty of games to mention that have poor graphics yet awesome gameplay, and I could start from the good old age of text adventures and the various DOS-era games. Do the games pong, pacman, breakout, tron ring a bell to you? Well, these games were the beginning for many things and they are still very enjoyable videogames, despite their truly pixeled graphics. And yes, I don't give a thit about the graphical difference between Warcraft 3 and Company of Heroes, despite the fact I would personally choose COH any day, because I prefer its gameplay than Warcraft III gameplay. I also prefer Warcraft 2 gameplay than Warcraft 3, despite its much-much worse graphics, because it had a true rts feeling while Warcraft 3 seems more like an RPG to me with all these heroes and items you can purchase (just my humble opinion).
Finally, people shouldn't make their minds based on vids. I don't care if they do, I really believe they shouldn't. By the way, I am NOT the exception of not judging games beacuse of their graphics, since there are a lot of "pixel-lovers" (like me!) who love old-retro games more than the modern ones.
Play TA:Kingdoms for a lot of hours and days, take a look to its manual, enjoy the cosmology and the storyline as well as its gameplay, listen to ist atmospheric music and at last judge its graphics in comparison with other RTS games of its era and you will see this game is not thit at all. Of course, this is true for almost every good, old, forgotten, underestimated game...