How can I alter a MenuItem on the Options Menu on Android?

For this type of operation I usually choose not to alter the menu items, but just hide the ones you don't need:

@Override
public boolean onPrepareOptionsMenu(Menu menu) {
    super.onPrepareOptionsMenu(menu);
    menu.findItem(R.id.start).setVisible(!isStarted);
    menu.findItem(R.id.stop).setVisible(isStarted);
    return true;
}

Flygenring answer is correct, but menu.findItem() is laggy and calling it within onPrepareOptionsMenu(Menu menu) produces bad user experience. It's better to get MenuItem object once while creating menu, and then just call setVisible each time menu occures on screen:

    MenuItem mDynamicMenuItem;

    @Override
    public boolean onCreateOptionsMenu(Menu menu) {
        // Inflate the menu; this adds items to the action bar if it is present.
        getMenuInflater().inflate(R.menu.main, menu);
        // Get dynamic menu item
        mDynamicMenuItem = menu.findItem(R.id.menu_item);
        return true;
    }

    // Prepare the Screen's standard options menu to be displayed. This is called right 
    // before the menu is shown, every time it is shown. You can use this method to
    // efficiently enable/disable items or otherwise dynamically modify the contents.
    @Override
    public boolean onPrepareOptionsMenu(Menu menu) {
        super.onPrepareOptionsMenu(menu);
        // Here is just a good place to update item
        mDynamicMenuItem.setVisible(isVisible);
        return true;
    }

You probably need to call super.onPrepareOptionsMenu after you are finished making your changes. From the docs:

Deriving classes should always call through to the base class implementation.

I got the solution. You are basically deleting the MenuItem when calling removeItem() thus also deleting the reference. Using this code works.

private boolean isStarted = false;

@Override
public boolean onOptionsItemSelected(MenuItem item) {
    switch (item.getItemId()) {
    case 1:
        isStarted = true;
        return true;
    case 0:
        isStarted = false;
        return true;
    default:
        return super.onOptionsItemSelected(item);
    }
}

@Override
public boolean onPrepareOptionsMenu(Menu menu) {

    if(isStarted) {
        menu.removeItem(1);
        menu.add(0, 0, 0, "Stop");
    } else {
        menu.removeItem(0);
        menu.add(0, 1, 0, "Start");
    }

    return super.onPrepareOptionsMenu(menu);
}

You have to create the MenuItem again. Thats also the reason for the false label. Actually you don't need the MenuInflater as you create the Menu via code so also no need for any menu XML file.

thanks for the info in this post as it solved my problem of the false labels in my menu. I did have to modify it slightly and have the final code that works well as follows in the hope it saves someone else some time and frustration. Its a slightly different solution but the main change I made was the .setVisible to either True or False, apart from that i.shadrins solution was the best fit for my needs.

    @Override
public boolean onPrepareOptionsMenu(Menu menu) {
    super.onPrepareOptionsMenu(menu);

    if(loggedIn) 
    {
        logIn.setVisible(false);
        logOut.setVisible(true);
    } 
    else 
    {
        logIn.setVisible(true);
        logOut.setVisible(false);
    }
    return true;
}


@Override
public boolean onCreateOptionsMenu(Menu menu) {
    super.onCreateOptionsMenu(menu);
    // Inflate the menu; this adds items to the action bar if it is present.
    getMenuInflater().inflate(R.menu.main, menu);
    logIn = menu.findItem(R.id.loggedOut);
    logOut = menu.findItem(R.id.loggedIn);
    return true;
}