You are likely having issues because you have only solved part of the CSS problem. There are 3 different templates that are used by the Menu and 2 of them are also used by other HTML helpers. For that reason, it might be a good idea to create named templates (as in the example answer below) to create separate templates for each HTML helper (Menu, SiteMapPath, SiteMap, etc). For each level of nodes, the Menu recursively calls the SiteMapNodeListHelper, which might not be producing the HTML that Bootstrap is expecting (depending on which of the nav options you are using).
See this answer for a starting point, and then you can modify the HTML and class attributes from there.
Keep in mind you can also use custom attributes to supply additional data (such as CSS class names) based on the node selected, or you can use the IsCurrentNode and IsInCurrentPath properties of the SiteMapNodeModel to determine if the current node is active, if needed.