I received quite a number of emails containing suggested names for Pluto's moons -- thanks! I just sent all the suggestions to Alan Stern; here they are for everybody's enjoyment. I'll be tickled if they end up picking any of these, though of course I'm sure they have their own ideas. The thing I'm most curious about is whether the IAU will relax their requirements and permit the re-use of a name that's already been given to an asteroid. So many great names already belong to asteroids, which is making it increasingly difficult to find names for moons (though one could debate which is more deserving of the great name, the asteroid or the moon, or whether anyone would really be confused by there being two objects, an asteroid and a moon, with the same name. It's not like people have any trouble telling the difference between Paris, France and Paris, Texas). Anyway, here's all the suggestions.
How about Minthe and Leuce for S/2005 P1 and S/2005 P2? Both were subjects of Pluto's "interest" and both probably killed by Persephone after which they were turned into mint and the poplar respectively.
The obvious thing to do would be to go for the rivers of Hell, and call the moon nearest Charon Acheron and the other one Lethe, but those are rather major mythological objects with which to associate two blocks of ice no larger than the bigger Saturnian ring-shepherd moons.
I hope Alan meant Greco-Roman names. Charon, after all, is Greek. There's been a suggestion going around that I think would be good because it would have a wonderful mnemonic for children, with the number of heads corresponding to the moon number. What better name for a medium-sized companion than Pluto's dog, Cerberus? Cerberus also has a brother, Orthrus. That may be a little tenuous, because Orthrus did not reside in Hades, but I'm hoping that the relationship with Cerberus will be enough. The mnemonic is this: One-headed Charon for Pluto I, Two-headed Orthrus for Pluto II, Three-headed Cerberus for Pluto III.
Chronos - God of Chaos, Father of Pluto. The Guy who ate his Children. Hades - another Name for Pluto. Demeter (aka Ceres; Goddess of Harvest) - in some Sense the "Counterpart" of Pluto, as Pluto is also the God of Wealth, who had to take care for Seeds buried in the Soil to germinate. Demeter has to take Care of all Plants above the Soil. Kore (Daughter of Demeter), as she became Goddess of the Underworld renamed to Persephone or Proserpina. She picked Flowers, as Pluto captured her. Demeter started to grief and all the Flowers and all Green started to fade away. Zeus/Jupiter sent Hermes/Mercury to Pluto for an Agreement: Persephone should stay two thirds of the year in this World to let the Flowers and Trees grow and during the rest of the year in the Winter, she should stay in the Underworld. Kore can also be found at the Ecliptic as Virgo, the Virgin. Kallirohe - Daughter of Okeanos; Friend of Kore. She was with Kore as she picked the Flowers. Erebos - Plutos "Kingdom" of Shadows. Pyriphlegethon - Castle of Pluto; Surrounded by three Walls and with a River of Fire around it. Cerberos - (or its Roman Pendant) the Three-Headed Dog of the Underworld, (gravitationally) chained to its Master, Pluto. In my Opinion Formations in the Plutonian System (which New Horizons will hopefully Discover) could also be Named after Characters and Places in the Myths around Life and Death from all around the World, such as Heaven, Elysium, Styx, Acheron, Kokytos, Gehenna, Hel, Glasir, Orpheus and Eurydike, (Walhalla can already be found on Callisto) and so on.
Typhon and Echinda. They are the parents of Cerberus. If there were only one new moon Cerberus would be perfect...
Hypnos (Sleep) and Thanatos (Death) were Pluto's assistants who also lived in the Underworld. They were either brothers or half-brothers (depending on the particular story) of Charon, with the same mother (Nyx - Night). They *are* Greek names rather than Roman - but so is Charon, and most of the other moons of the Solar System.
Proserpina and Libera. Proserpina is the Roman name for the Greek goddess Persephone, and she was abducted by Pluto...causing Ceres (Demeter in Greek myth) to create winter in her grief. Libera is a Roman goddess who is the wife of Liber, the old Italian god of fertility and growth in nature. Libera was gradually equated with Proserpina in Roman myth, and this is why I think Libera and Proserpina would be interesting names for Pluto's new satellites.
Interesting little problem to ponder, especially since so many appropriate names have already been used for asteroids. Obvious favorites such as the three headed guard-dog to the Underworld, Cerberus, Pluto's consort, Proserpina (Roman equivalent of Persephone), and her mother, Ceres, have all been used (1865 Cerebus, 26 Prosperina and 1 Ceres.)
The three judges of the souls in the underworld would seem like good options, especially the brothers Minos and Rhadamanthus, were it not for 38083 Rhadamanthus and 6239 Minos. The third judge, Aeacus, although unused, seems less appropriate without his companion judges.
The eternally damned souls of Tantalus and Sisyphus who reside in the classical underworld would be great, especially given the poetic similarity of orbital motion to Sisyphus' perpetual pushing of a rock, except for the existence of 2102 Tantalus and 1866 Sisyphus. One could use two of the important rivers of the Roman Underworld; Acheron, Cocythus, Phlegethon, Styx or Lethe. They haven't been taken and they did surround the palace of Pluto and the underworld so they seem somewhat poetically appropriate, however, naming the moons after geographical features as opposed to mythical beings seems without precedent and you'd have the awkward arrangement of having Charon being encountered "beyond" the "rivers," when moving towards Pluto, when it should be the other way around.
Although the obvious ones aren't usable, a quick read of the Aeneid, the very heart of distinctly Roman mythology, turns up two very excellent options; Briareus and Geryon. One finds reference to them in book VI where Aeneas visits the underworld. To do so he must pass through the Cumaean gate to the Underworld which is guarded by many manner of spirit and apparition.
"Of various forms unnumber'd specters more, Centaurs, and double shapes, besiege the door. Before the passage, horrid Hydra stands, and Briareus with all his hundred hands; Gorgons, Geryon with his triple frame; and vain Chimaera vomits empty flame."
There is already a Hydra constellation and 623 Chimaera but there is, as of yet, no celestial reference to Briareus and Geryon (Gorgon is also unused but that refers to a type of creature not a specific being). Briareus was one of the Hecatonchires who were giants with a hundred arms and fifty heads and incredible strength and ferocity. Geryon was a Titan with three heads, three bodies, and six arms and is best known from the story of the Twelve Labours of Hercules where the 10th labour was to steal the Cattle of Geryon. They come directly from a prime text of Roman mythology, they are logically connected to each other as apparitional guardians of the Cumaean gate to the underworld and also as they are both multi-bodied beings, and they fit very appropriately into the Pluto - Charon system as they were sentries to Pluto's realm and ones that a traveler would encounter before meeting Charon, as a spacecraft traveling to Pluto would pass the orbits of S/2005 P1 and S/2005 P2 before Charon. Also, the names sound really cool.
Two other Pluto connected names that haven't been used yet are Mors (the Roman personification of Death) and Somnus (the Roman personification of sleep) who were brothers and resided in the underworld, however, it would seem to me a bit of an unnecessarily morbid choice and not nearly as exciting as multi-headed, multi-armed giant-guards to the underworld.