Un nombre es algo que debes crear a través de lo que dicho personaje exprese o quiera expresar. Hay muchos métodos para sacarte nombres rápidos sin necesidad de tener una imaginación desbordante.
1) Como ya han dicho antes, usar nombres comunes, a veces lo común puede resultar más sencillo para el lector y más fácil para recordar y quedarse con el mismo. Sólo usa nombre de gente que conozcas y nombres extranjeros típicos con apellidos también típicos que pueden ser adjetivos, sustantivos o lugares que suenen bien, piensa que es muy normal, sobre todo en literatura fantástica medieval, que a una persona se le conozca del lugar que viene y que junto a su nombre diga su lugar de procedencia.
2) Traducir palabras en español a otros idiomas. Tan simple como eso. Llamarle a alguien "Guerrero"; queda muy mal, pero si se llama "Krieger"; da todo el pego. Simplemente he traducido guerrero al alemán y obtienes un buen resultado, además, así su nombre representa lo que es o cómo es, en este caso, si es el nombre de un luchador, Krieger queda bastante bien. Y siempre puedes modificar algo que obtienes levemente para que no sea tan cantoso, por ejemplo en lugar de Krieger; pones Kreger o Kreg y aunque ahora su nombre no signifique nada, queda bien y tiene unos orígenes, todo gracias a un diccionario online.
3) Palabras compuestas. Esto viene muy bien para localizaciones, ciudades, poblados, tipo de personas. Como han dicho antes, a un grupo de hombres se les llama Fremen, un compuesto de Free Man (hombre libre). O por ejemplo a un manantial o una fuente de un agua especial, le llamas al sitio donde se encuentra "Wavine", que digamos que por su pronunciación lo pueden cambiar a "Wavin", y te ha sido tan fácil como juntar "Water" y "Divine". Por supuesto todos estos ejemplos me los estoy inventando sobre la marcha y a lo mejor no son los más acertados o pueden no gustar, pero se supone que ya es cosa tuya buscarte algo mejor esto son ejemplos xD.
4) Destaca su principal característica. Si una ciudad está rodeada de pinos, llamale Pineda o Pinoplia o cualquier maldita combinación irracional que te surga de tu mente a partir de la variación de la palabra pino xD. Si un hombre es muy sabio, puedes llamarlo Sab, o variarlo en cosas raras como Seb, Seviar, Sabier, Sabrum... A partir de una idea el resto es derivarla.
Bueno. Si te fijas la idea es tener una base y luego variar, variar y variar por dónde quiera que puedas, a través de otros idiomas, de mezclas con otras palabras, mezclar idiomas, variar vocales, cambiar silabas. Mira, lo que no puedes pretender es que simplemente por tu imaginación te vaya a surgir todo, no puede salir nada de la nada y no puedes sacarte el historion del siglo pensando en tu cama. Para que te surgan personajes, lugares, acontecimientos, fenómenos y demás parafernalia, además de mucha imaginación, necesitas ver cosas, leer cosas, tocar cosas, conocer cosas, etc... Tienes que ver las cosas de otra manera, no te limites a verlas y aceptarlas como son, míralas e imagínate como deberían ser para que se amolden a ti. La gente se amolda al mundo, los artistas amoldan el mundo.