backNaming, like all good things in the Roman world, is complex.
Roman Names
Roman male citizens generally had three names, the praenomen, nomen, and cognomen. They are roughly equivelant to the modern first name, last (or family) name, and nickname. So I might be Christopher Hall Chris in the Roman world (though the Roman first name and nickname didn't have anything to do with each other). Not everyone had a cognomen; Mark Anthony, for instance, did not. At home a man would probably be known by his praenomen, his friends might refer to him by either his nomen or, for very good friends, his cognomen. The cognomen often described a personal characteristic (Rufus (redhaired) or Brutus (idiot)). The cognomen could also be used as an honorific (Germanicus (fighter of Germans)). A Gaul who became a citizen might take the emperor's nomen as his own.
Women and slaves had an easier time of it, they only had one name. A slave generally had a personal name, that became his cognomen if he were freed. The slave took his master's praenomen and nomen as his own. Women could have one name or two, but they were always based on her father's name, the nomen and possibly the cognomen, in the feminine form. So Titus Flavius Domitianus might have a daughter named Flavia Domitiana or a daughter named Flavia. His slave Gallic slave might be Verucloetius, if the slave was freed his name would become Titus Flavius Verucloetius. If a man had multiple daughters they would all have the same name, so they might be called "the elder" and "the younger" or even "the first", "the second", "the third", etc. Though it is not suported by the historical record, it is not implausible to assume that women had cognomens other than a simple number, used in the company of other women or in their close family. We will assume that all immortals and many mortals used such unofficial cognomens.
Praenomens
(these are the only praenomens in common usage)
Aulus
Appius
Gaius
Gnaeus
Decimus
Lucius
Marcus
Manius
Nero
Publius
Quintus
Servius
Sextus
Spurius
Titus
Tiberius
Vibius
Nomens
Accius
Aelianus
Aelius
Aemilius
Annaeus
Antistius
Apuleius
Arrianus
Asinius
Calpurnius
Cassius
Claudius
Cornelius
Cremutius
Curtius
Ennius
Fabius
Flavius
Gabinius
Gavius
Gellius
Hirtius
Horatius
Julius
Junius
Labienus
Laberius
Licinius
Livius
Lucretius
Marius
Marcellus
Mestrius
Mucius
Persius
Petronius
Piso
Pomponius
Porcius
Propertius
Remmius
Sallustius
Terentius
Tullius
Valerius
Varius
Velleius
Cognomens
(Translations supplied where I can find them)
Africanus (warrior in Africa)
Andronicus
Apicius
Aristides (ears of corn)
Balbus (stamering)
Brutus (idiot)
Caecus (blind)
Calvus (bald)
Carus (beloved)
Cato (sly)
Catullus (puppy-like)
Celsus (eminent)
Cordus (great mind)
Crispus (quivering)
Donatus (presentable)
Flaccus (fat?)
Frontinus
Gallus (rooster)
Germanicus (warrior in Germany)
Herculius (Hercules-like)
Labeo
Lucanus
Macer (thin)
Martialis (Mars-like)
Maximus (great)
Naso
Niger (dark)
Paterculus
Pictor (painter)
Plautus
Pollio
Probus (virtuous)
Quintilianus
Rufus (red-haired)
Scaevola
Secundus (the second)
Siculus
Sisenna
Tiro (novice)
Tranquillus (calm)
Troucillus
Gallic Names
The Gaul's generally only had two names, a personal name and a tribal name. Women's names can be found by feminizing the male personal names in the Roman fashion. That will get close enough at least.
Personal Names
Diviciacus
Divico
Dumnorix
Liscus
Nammeius
Nepos
Orgetorix
Verucloetius
Tribal Names
(for southern Gaul)
Allobroges
Cadurci
Helvetii
Ligures
Ruteni
Tolosates
Volcae
Other Names
Here are some other names pulled from around the empire for your enjoyment
Carthegenian
(These are not used by the mortal population, but are used by the Lasombra)
(As near as I can tell there are only about six Carthegenian names, and four
of them start with "H")
Hadrisul
Hamilcar
Hannibul
Hanno
Mago
Maharbal
Greek
Appianos
Crinagoras
Dionysius
Dioscurides
Epictetus
Galenos
Polyaenus
Polybius
Soranus
Strabo
Zosimus