Get Zanzibar and rename it to what you want. Open Zanzibar with hex editor. Go to offset 0x1bc. You should see scenarios\multi\zanzibar\zanzibar change zanzibar\zanzibar to something like mymap\mymap. Now open mainmenu.map and go to "matg"(Globals) tag and change the value to an unused value. There is only 11 maps so 12 would be the next. Now change the name and description to whatever you want. For Scenario Name put scenarios\multi\mymap\mymap or whatever you named it as and in Next value use the value you used before. Now resign it and send it to your box and that should work.
P.S. Were it says mymap, this can be changed to whatever you want to name it as.
I think this is done best with DotHalo. Also, I learned this from a tut written by farklem.
I also found that tut that you copied all that info from.
But when I open the map up in Dothalo, I can't get the Hexeditor window to populate.
Nor can I get the "add map to mainmenu" button to become un-grayed out.