I've done that myself - it's acctually really easy.
AdminCP>Styles and Templates>Style Manager> Edit Templates (click the little [<< >>] button next to the style you want to edit)
Navigation/Breadcrumbs Template>navbar
When in the template, find;
<!-- nav buttons bar -->
<div align="center">
<table class="tborder" cellpadding="$stylevar[cellpadding]" cellspacing="$stylevar[cellspacing]" border="0" width="100%">
<tr align="center">
<if condition="$show['member']">
<td class="vbmenu_control"><a href="usercp.php$session[sessionurl_q]">$vbphrase[user_cp]</a></td>
</if>
<if condition="$show['registerbutton']">
<td class="vbmenu_control"><a href="register.php$session[sessionurl_q]" rel="nofollow">$vbphrase[register]</a></td>
</if>
<td class="vbmenu_control"><a href="faq.php$session[sessionurl_q]" accesskey="5">$vbphrase[faq]</a></td>
<td class="vbmenu_control"><a href="memberlist.php$session[sessionurl_q]">$vbphrase[members_list]</a></td>
<td class="vbmenu_control"><a href="calendar.php$session[sessionurl_q]">$vbphrase[calendar]</a></td>
<if condition="$show['popups']">
<if condition="$show['searchbuttons']">
<if condition="$show['member']">
<td class="vbmenu_control"><a href="search.php?$session[sessionurl]do=getnew" accesskey="2">$vbphrase[new_posts_nav]</a></td>
<else />
<td class="vbmenu_control"><a href="search.php?$session[sessionurl]do=getdaily" accesskey="2">$vbphrase[todays_posts]</a></td>
</if>
<td id="navbar_search" class="vbmenu_control"><a href="search.php$session[sessionurl_q]" accesskey="4" rel="nofollow">$vbphrase[search]</a> <script type="text/javascript"> vbmenu_register("navbar_search"); </script></td>
</if>
<if condition="$bbuserinfo['userid']">
<td id="usercptools" class="vbmenu_control"><a href="$show[nojs_link]#usercptools">$vbphrase[quick_links]</a> <script type="text/javascript"> vbmenu_register("usercptools"); </script></td>
</if>
<else />
<if condition="$show['searchbuttons']">
<td class="vbmenu_control"><a href="search.php$session[sessionurl_q]" accesskey="4">$vbphrase[search]</a></td>
<if condition="$show['member']">
<td class="vbmenu_control"><a href="search.php?$session[sessionurl]do=getnew" accesskey="2">$vbphrase[new_posts_nav]</a></td>
<else />
<td class="vbmenu_control"><a href="search.php?$session[sessionurl]do=getdaily" accesskey="2">$vbphrase[todays_posts]</a></td>
</if>
</if>
<td class="vbmenu_control"><a href="forumdisplay.php?$session[sessionurl]do=markread" rel="nofollow">$vbphrase[mark_forums_read]</a></td>
<if condition="$bbuserinfo['userid']">
<td class="vbmenu_control"><a href="#" onclick="window.open('misc.php?$session[sessionurl]do=buddylist&focus=1','buddylist','statusbar=no,me nubar=no,toolbar=no,scrollbars=yes,resizable=yes,w idth=250,height=300'); return false;">$vbphrase[open_buddy_list]</a></td>
</if>
</if>
<if condition="$bbuserinfo['userid']">
<td class="vbmenu_control"><a href="login.php?$session[sessionurl]do=logout&logouthash=$bbuserinfo[logouthash]" onclick="return log_out()">$vbphrase[log_out]</a></td>
</if>
</tr>
</table>
</div>
<!-- / nav buttons bar -->
Notice the little notes that tell you waht it is, just grab everything between them then put it above;
<!-- breadcrumb, login, pm info -->
<table class="tborder" cellpadding="$stylevar[cellpadding]" cellspacing="$stylevar[cellspacing]" border="0" width="100%" align="center">
<tr>
<td class="alt1" width="100%">
<if condition="is_array($navbits)">
<table cellpadding="0" cellspacing="0" border="0">
<tr valign="bottom">
<td><a href="#" onclick="history.back(1); return false;"><img src="$stylevar[imgdir_misc]/navbits_start.gif" alt="$vbphrase[go_back]" border="0" /></a></td>
<td> </td>
<td width="100%"><span class="navbar"><a href="$vboptions[forumhome].php$session[sessionurl_q]" accesskey="1">$vboptions[bbtitle]</a></span> $navbits[breadcrumb]</td>
</tr>
<tr>
<td class="navbar" style="font-size:10pt; padding-top:1px" colspan="3"><a href="$scriptpath"><img class="inlineimg" src="$stylevar[imgdir_misc]/navbits_finallink.gif" alt="$vbphrase[reload_this_page]" border="0" /></a> <strong>$navbits[lastelement]</strong></td>
</tr>
</table>
<else />
<div class="navbar" style="font-size:10pt"><a href="$vboptions[forumhome].php$session[sessionurl_q]" accesskey="1"><img class="inlineimg" src="$stylevar[imgdir_misc]/navbits_start.gif" alt="" border="0" /></a> <strong>$vboptions[bbtitle]</strong></div>
</if>
</td>
<if condition="$bbuserinfo['userid']">
<td class="alt2" valign="top" nowrap="nowrap">
<div class="smallfont">
<strong><phrase 1="$bbuserinfo[username]">$vbphrase[welcome_x]</phrase></strong><br />
<phrase 1="$pmbox[lastvisitdate]" 2="$pmbox[lastvisittime]">$vbphrase[last_visited_x_at_y]</phrase>
<if condition="$show['pmstats']"><br /><phrase 1="$vbphrase[unread_x_nav_compiled]" 2="$vbphrase[total_x_nav_compiled]" 3="$session[sessionurl_q]">$vbphrase[private_messages_nav]</phrase></if>
</div>
</td>
<else />
<td class="alt2" nowrap="nowrap" style="padding:0px">
<!-- login form -->
<form action="login.php" method="post" onsubmit="md5hash(vb_login_password, vb_login_md5password, vb_login_md5password_utf, $show[nopasswordempty])">
<script type="text/javascript" src="clientscript/vbulletin_md5.js"></script>
<table cellpadding="0" cellspacing="$stylevar[formspacer]" border="0">
<tr>
<td class="smallfont">$vbphrase[username]</td>
<td><input type="text" class="bginput" style="font-size: 11px" name="vb_login_username" id="navbar_username" size="10" accesskey="u" tabindex="101" value="$vbphrase[username]" onfocus="if (this.value == '$vbphrase[username]') this.value = '';" /></td>
<td class="smallfont" colspan="2" nowrap="nowrap"><label for="cb_cookieuser_navbar"><input type="checkbox" name="cookieuser" value="1" tabindex="103" id="cb_cookieuser_navbar" accesskey="c" />$vbphrase[remember_me]</label></td>
</tr>
<tr>
<td class="smallfont">$vbphrase[password]</td>
<td><input type="password" class="bginput" style="font-size: 11px" name="vb_login_password" size="10" accesskey="p" tabindex="102" /></td>
<td><input type="submit" class="button" value="$vbphrase[log_in]" tabindex="104" title="$vbphrase[enter_username_to_login_or_register]" accesskey="s" /></td>
</tr>
</table>
<input type="hidden" name="s" value="$session[sessionhash]" />
<input type="hidden" name="do" value="login" />
<input type="hidden" name="vb_login_md5password" />
<input type="hidden" name="vb_login_md5password_utf" />
</form>
<!-- / login form -->
</td>
</if>
</tr>
</table>
<!-- / breadcrumb, login, pm info -->
And there you have it.
Note - I can't remember if the Navbar is in the same table as the Breadcrumb by default, so you might have to manually make it on it's own table (or you can just delete your code [!!ONLY BETWEEN THE NOTES!!] and C&P mine in there. I don't use any customisations for the Navbar so if you don't either, everything should be hunky dory.
www.gekitou.org/forum <-- Link to my forum, how it sould look once finished (minus the custom colours).
EDIT: Fixed up the bad PHP tag.
EDIT2: Oh, it would be a good idea to drag the notes along with the code, just so you can find it all again later :p
Kovash - That worked prefectly. When I tried to figure this out on my own I was moving everything that was moving everything related to that bar to the top even "<!-- NAVBAR POPUP MENUS -->" and such which is what was messing me up.
Thanks so much!
-Michael