I can actually generate names spontaneously, and they're pretty spiffy. I've not have a hard time figuring out a name for my characters. But here are my main FH character names and their origins:
Telluris: I named him after the Latin name for earth (Masculine).
Telly: Derived from Telluris.
Jorhaal: No idea, I was thinking up a name that was almost northern European. Although the Sanskrit word 'Jora' Seems to reflect some of her aspects quite well, it was never thought of.
Ferro: Named after Ferrum, Latin for Iron (Neutral). Altered it a little because I don't want to name her Ferra/Feara (a name taken by my friend's character).
Leknu: Originally Lignus, which is also another Latin word for timber (Masculine), altered it a little to be less obvious.
Iska/Iskandre: Probably from Iskandar, which is Alexander the Great's given name in Eastern countries. Slightly altered.
Aclediptus: Spontaneous, I wanted to think up of something Latin (like the rest of my characters) And this came to me.