Isn't it more like being an artist now? I mean, using Photoshop more like an artist's canvas... For instance, have a palette of colors (Swatches work wonders here), set the opacity to something low (50% I guess?) and try using one of the brushes meant for stroking, then continuously stroke a few bits here and there. I'm not really sure.
You can also use Burn tools to create some shading, or you can simply brush more.
Hn...Wait, what kind of design you're going for? A physical sort of map, with all the visible landscape types there and whatnot? Or some political map (i.e. only the country borders and maybe some mountains)? Eh, I guess you're probably leaning towards the former huh? I really do feel like this is more art than anything else...Sorry. @_@
What tutorials have you tried? A search yielded this one, but chances are you already did it.
http://www.cartographersguild.com/showthread.php?2557-Award-Winner-Making-maps-in-PhotoshopWish I can help you anymore mate, but I'm not thinking right at this moment.