Releasing new plugin version, how to rename old options keys?

You should store a version number for your plugin in the database (if you don’t already, add this pronto), using that you can do this (note that this is pseudocode):

if( $db_version < {your desired version} ) {
    // previous updates and such
    $db_version = $new_version; //put that in the database
}
if( $db_version < $current_version ) {
    create $options array
    foreach( $option as $o ) {
        if( get_option( $o['old_name'] ) ) {
            update_option( $o['new_name'], get_option( $o['old_name'] ) );
            delete_option( $o['old_name'] ); //clean up behind yourself
        }
    }
    and then update your database version again
}

Then, when you release your next update, you change $current_version to the version in which the change happened. The reason behind using this method is that if your updates are ever incrimental (which is to say, you can’t go from 1.1 to 1.9, you have to hit 1.3 and 1.5 in between or something like that), you will have a structure in place to manage that. If it gets complex, I’ll often keep the code clean and just have the if statement execute something like wpse49717_plugin_release_150() and manage the updates and such with that.

I’d just like to note (well, really, reiterate) that you should only be using this structure for your incrimental updates. You should wholly expect this code to only be run ONCE, so make sure you’re updating your database versions and such.