Are the items in your menu static or do they come from your database? If the links are coming from your db you could potentially rework the query to get the items organized by the category. If you have a column in your table that holds a color value you could make use of this color value in a custom applied style for the menu item.
Please explain a little more about your situation and how the menus are crafted and if you can post back with a link to the vertical menu so we have a better idea of what you are starting with.
As for the second menu not showing correctly there should be no limitation to having multiple menus on the page. There is probably some missing or incorrectly placed css references that are causing this problem. A link to the page would be most helpful in determining what is wrong.
