I also vote for the Lich. In my opinion it's still the best because it's generic enough so that you can make anything out of it (especiall since it doesn't have to be human), and it has the added flavor of someone who actually wanted to become undead and succeeded.
A Death Knight is ok, but usually it gives me the feeling of being a pawn rather than the mind behind a horde, and as such I tend to use them (or similar warrior undead) as the ones who lead the army while the true "boss" stays in the fortress.
A Vampire IMHO has the disadvantage of being too much defined. As pointed out already, what vampires do is hunting mortals for blood, which may railroad the story too much. Vampires need mortals, so if you have a realm totally made of undead, that's the last place a Vampire would like to live
unless they keep mortal cattle... Because of this, they are fantastic villains in adventures of intrigue, hunting and stealth, but I don't picture them very well as a king of an undead realm.
Other very powerful undead which are very supernatural (the Atropal, the Deathbringer, or an undead fiend/deity) they could be definitely fearful, but IMO they would do better as something otherwordly which is worshipped by the kingdom including the king - its first servitor. Eventually it may be the true overmind, but perhaps without physical access to the mortal world until some great scheme is accomplished, and here enters the king's job. Well, this is quite a typical idea after all, even Warcraft is similar...
