Click on ‘Appearance’ in the menu. A list of items should drop down such as "Themes", etc. One of these is named "Menu". Click on menu, and you should see your custom post type on the left somewhere. Click the "show all" tab and you should see your 4 categories. Tick them and click "Add to menu". Save the menu.
(I’m assuming your theme supports the wordpress 3 menu)
Is this what you meant?