The maps I have done are all for the fantasy world I created. I have been writing a story since 2002 and I started mapping out stuff later. I only had a couple of rough sketches.
Don't name everything, a lot of places in my world don't have a name either. You don't want to clutter your maps too much anyway, unless you are going for an atlass style map. I found naming stuff difficult as well. That's why the names of places of interest in my world have simple, logical names, like "Greenwood" for a city located in large woods and "Northgate" for a town that lies to the north. I also used the fantasy name generator to get some more exotic names:
http://www.rinkworks.com/namegen/
Oh, and I cheated a bit, as the overland map I needed didn't have any continents or seas