A lot of people recommend AGAINST meaningful names since attackers can use them to better target their attacks (although arguably it is normally trivial to figure out what is what anyway).
If you're going to have meaningless names then I just leave the default (e.g. rack123.server456) since no matter if you use planets, characters, or toys you'll still ultimately end up using its function to describe it or its IP address anyway.
Realistically your servers and their purpose should be tracked internally via some kind of system (be it Google Apps Spreadsheet, intranet page, resource tracking system, or similar). Which makes the actual host name meaningless.
That led to memorable names such as Mars, Venus, Pluto and Ganymede that didn't conflict much with other namespaces.
e.g. lon1prodapp001, lon1testdbs001, nyc1testweb001
And here's a regex that describes it: http://rubular.com/r/rdEZU9qJ6L
I hate meaningless server names. It's cute for the first 3 but once you're over 10 you won't remember the difference between the 'obsidian' and 'sovite' servers. Which one is production and which one is dev test again?
At least with a logical naming scheme, you'll have a reasonable idea whether you're even on the right server or not.
If you have lots of servers you can only use machine generated names with some kind of role indicator. For fewer servers you can pick something nicer.
For fewer and more specialised machines I'll think of something I like, my private machines are named after the deities of the Cthulhu Mythos (azathoth, cthulhu, shub, hastur, lloygor, nyarlathotep), while some of our Office servers get their names based on dinosaurs and other prehistoric animals.