i've got a lvl 17 warrior on Azgalor and a lvl 8 paladin on Burning Legion.
it's really, really fun. but beware: soloing sucks. if you're going to play it, get in some sort of group. about ten of my friends are doing it and we group, though they're starting to pull ahead because i work more than they do and i have to fine time to WORK OUT, DIRK!
my guild waited until the first night before choosing a server, so we got onto one that had only been open an hour or two. i've only had to wait in a queue once, though all the servers have connection issues.
paladin is great, but warrior leaves a bit to be desired. a mage in bear form or a good paladin can tank just as well as a warrior now, so i'm almost a useless class. but we'll get buffed sometime when enough people complain.