You could probably do this, but it would be hard to edit the map afterwards. One of my advantage is that I used one of these computer pen, so it was easier to draw the map. As for what program I used, I used flash... not a very good choice, I just happen to know how it works. What you want for a good mapmaking graphic editor is the ability to work with layers. You can do that in photoshop, its just that photoshop is hard to learn (i should have done my map in photoshop, but i was too lazy to learn it hah). It is possible to make your map in paint, but it would also be hard, and unless you spend a lot of time on it it wouldn't look very professional. My suggestion is the following: get yourself some
copy of photoshop, google for a basic tutorial or check if one is included and you should be able to start your map. I think that what is the most important is to get a sketch version up as soon as possible. When you actually post a map, however ugly or basic it is, you can start to receive advice from other users, and this will make your time much, much easier. But start by learning the basics of photoshop or another program like that, and then play around a bit with sketching your map.