You can make excellent maps with a normal graphics program like Photoshop, Paint Shop Pro or Gimp (free!). It has the disadvantage that you don't have the big libraries of map-elements, but you can find a lot of stuff on the net and you can use these programs for other things, too.
You can find a decent look into the basic map-making functions at this short tutorial: http://www.the-holocron.com/index.php?option=com_content&task=view&id=32&Itemid=48 (even though some images are missing).