Hello Juan, menu entries are stored as records of the 'ir.ui.menu' object type, so it is possible to use 'record' XML tags to update 'ir.ui.menu' records by providing 'model' and 'id' attributes to identify the existing record. E.g. Project>Configuration (source here):

    <record model="ir.ui.menu" id="mod_id.menu_id">
      <field name="name">My New Menu Name</field>
    </record>

'record' XML tags are processed differently, so you only require to provide fields/values for anything you want to modify.

Regards,
Marvin

Edit: I created a simple module 'hr_menu_mv' to shorten the top level "Human Resources" menu to "HR", just to verify this approach, below are sources for the three files required (verified with v7.0 and v8.0):

__init__.py:

# empty as no python modules are required to be imported

__openerp__.py:

{
    'name': "HR Menu Mv",
    'version': "0.1",
    'category': "Human Resources",
    'depends': ['hr'],
    'data': ['hr_menu_mv_view.xml'],
    'installable': True,
    'auto_install': False,
    'application': False,
}

hr_menu_mv_view.xml:

<?xml version="1.0" encoding="utf-8"?>
<openerp>
    <data>
        <record model="ir.ui.menu" id="hr.menu_hr_root">
            <field name="name">HR</field>
        </record>
    </data>
</openerp>

I'm omitting translations just to keep the example small and readable.

Try this:-

<menuitem name="New String"
    id="sale.menu_base_partner"
    groups="base.group_sale_salesman"
    sequence="20"/>

if you want to override a id youn need to set the complete id module.id

Do not forget insert into

<data noupdate="0">
<record model="ir.ui.menu" id="hr.menu_hr_root">
    <field name="name">HR</field>
<!-- in 11 version -->
    <field name="complete_name">HR</field>
</record>
</data>

to force the update of registry and CTRL+f5 in web browser to update the display name

I had the same problem, after trying all the methods none worked. Finally I realized that there was a translation problem as the menuitem name term was already translated, therefor although the changes were made correctly they were not visible. Check out the tranlsation terms to check if your menu name is already there. The method I finally used was: 

<menuitem name="Sales"
        id="account.menu_finance_receivables"
        parent="account.menu_finance"
        sequence="2"/>

Using an SQL Manager I would open ir_ui_menu and ir_ui_menu_group_rel and delete all records related to this particular Menu. Then ammend my template and update

Try code below. Paying attantion to my bold text. The two must be exact. If you put base.menu_base_partner on the first one then the bottom one must also be base.menu_base_partner

<menuitem name="My new string"
    id="menu_base_partner"
    groups="base.group_sale_salesman"
    sequence="20"/>
<menuitem id="base.menu_sales" parent="menu_base_partner" name="My new string" sequence="1" />