Editing a Custom Block
You get the delete option in the block configuration page for those blocks that have been created using Add Block option (in Admin >> Site Building >> Block). In your case the menu block in question might have been created programatically using hook_block or any other means that I'm not aware of and the Delete link might not appear due to the same. Suggest that you identify the code/module responsible for generating the block before you proceed on to anything. Also if you wish to replace this block with something more easily configurable I'd suggest using Nice Menus which I feel is a wonderful module