You could also consider to compile your own version. Try http://getbootstrap.com/customize/ (which has a apart section for the Navbars settings (Default navbar and Inverted Navbar)) or download your own copy from https://github.com/twbs/bootstrap.
You will find the navbar settings in variables.less. navbar.less is used to compile the navbar (depends on variables.less and mixins.less).
Copy the 'navbar-default section' and fill in your own color settings. Changing the variables in variables.less will be the easiest way (changing the default or inverse navbar won't be a problem because you have one navbar per page only).
You won't change all settings in most cases:
// Navbar
// -------------------------
// Basics of a navbar
@navbar-height: 50px;
@navbar-margin-bottom: @line-height-computed;
@navbar-default-color: #777;
@navbar-default-bg: #f8f8f8;
@navbar-default-border: darken(@navbar-default-bg, 6.5%);
@navbar-border-radius: @border-radius-base;
@navbar-padding-horizontal: floor(@grid-gutter-width / 2);
@navbar-padding-vertical: ((@navbar-height - @line-height-computed) / 2);
// Navbar links
@navbar-default-link-color: #777;
@navbar-default-link-hover-color: #333;
@navbar-default-link-hover-bg: transparent;
@navbar-default-link-active-color: #555;
@navbar-default-link-active-bg: darken(@navbar-default-bg, 6.5%);
@navbar-default-link-disabled-color: #ccc;
@navbar-default-link-disabled-bg: transparent;
// Navbar brand label
@navbar-default-brand-color: @navbar-default-link-color;
@navbar-default-brand-hover-color: darken(@navbar-default-link-color, 10%);
@navbar-default-brand-hover-bg: transparent;
// Navbar toggle
@navbar-default-toggle-hover-bg: #ddd;
@navbar-default-toggle-icon-bar-bg: #ccc;
@navbar-default-toggle-border-color: #ddd;
You could also try http://twitterbootstrap3navbars.w3masters.nl/. This tool generates CSS code for your custom navbar. Optionally, you could also add gradient colors and borders to the navbar.