Hi Lonelywanderer - that's a really nice start.
One easy way to colour the map is to just overlay lots of textures on top of each other in new layers. Use a soft eraser at varying opacities (I dont' think you have layer masks in elements) to let the textures you want to show through. Make sure you play with the blending modes and the opacities of the layers themselves as well.
To make a map appear huge, you'll need to make it very detailed (large resolution required) and it helps the illusion if you have lots of labels. Do a search on the forum for Bohunk's maps, he's a real master at creating the illusion of massive areas of land.
Just shout if you need any more help / elaboration.