Another option would be to start from a clean base by
- removing the blocks
- recreating them
This is what I personnally prefer as, then, the full layout updates are in the local.xml which is then more easy to read and understand for maintenance. This also may avoid conflicts in blocks nesting as my solution proposes to rename them (top.links => right.links, top.search => right.search, top.nav => right.nav). But this is just my opinion based on my experiences :)

So here is the local.xml I've successfully tried on a Magento 1.7.0.1
<layout version="0.1.0">
<default>
<reference name="header">
<remove name="top.menu"/>
<remove name="top.search"/>
<remove name="top.links"/>
</reference>
<reference name="right">
<block type="core/text_list" name="right.menu" as="topMenu" translate="label" before="-">
<label>Navigation Bar</label>
<block type="page/html_topmenu" name="catalog.rightnav" template="page/html/topmenu.phtml"/>
</block>
<block type="page/template_links" name="right.links" as="rightLinks" after="right.menu">
<action method="addLink" translate="label title" module="customer"><label>My Account</label><url helper="customer/getAccountUrl"/><title>My Account</title><prepare/><urlParams/><position>10</position></action>
<block type="wishlist/links" name="wishlist_link" />
<action method="addLinkBlock"><blockName>wishlist_link</blockName></action>
<block type="checkout/links" name="checkout_cart_link">
<action method="addCartLink"></action>
<action method="addCheckoutLink"></action>
</block>
</block>
<block type="core/template" name="right.search" as="rightSearch" template="catalogsearch/form.mini.phtml" after="right.links"/>
</reference>
</default>
<customer_logged_in>
<reference name="right.links">
<action method="addLink" translate="label title" module="customer"><label>Log Out</label><url helper="customer/getLogoutUrl"/><title>Log Out</title><prepare/><urlParams/><position>100</position></action>
</reference>
</customer_logged_in>
<customer_logged_out>
<reference name="right.links">
<action method="addLink" translate="label title" module="customer"><label>Log In</label><url helper="customer/getLoginUrl"/><title>Log In</title><prepare/><urlParams/><position>100</position></action>
</reference>
</customer_logged_out>
</layout>