Since your whole world is 3D, have you thought about doing the map / terrain in 3D too ? Generally most of us here make a terrain map in 3D and use different software to color it up based on heights and stuff. Doing rivers in 3D is much easier than 2D cos to some extent you can get the PC to calculate the correct positions for them.
In my sig is my GeoTerSys. Theres also another link to the keyword index where you can lookup Wilbur and Fractal Terrains for maps. Theres a whole bunch of software to do 3D terrains tho like L3DT, GeoControl, GlobalMapper, WorldMachine etc. Once you have some good terrain then Terragen is pretty good at getting some neat procedural textures applied to it. A chap of your skill should be able to handle any of these no problem.
EDIT -- on another point, your rivers in your maps are pretty wacky. Theres some tutorials about for doing rivers with proper physics. I think they would help out a lot.