On my map of Paidixira, the world is supposed to have a decidedly greek influence, so i kept a nifty greek translator site on bookmark at all times and translated a couple words together any time I needed a name. I went the same direction naming animals too: a hound with an axe shaped head is called a Xikouri combining the greek words for "axe" and "hound." I also recommend the site Behind The Name for anyone struggling to come up with forenames for characters. Not only do they have the etymology of thousands of names, but they also have tons of statistics and historical connections about names.

I've found things to be decidedly easier when taking from established languages. Behind all of the names i've made, I recognize the whisper of a real city or country. Some of the names have come out looking very alien (for example, trying to name forests often uses the root "Xylo" for wood, which has the odd effect of obscuring the meaning of a name whenever I use it.) but i'm using a blunt tool and one can't expect too much. I'm interested in using some of the techniques mentioned in this thread, so i hope my two cents have at least a glimmer of the usefulness your suggestions did.