I've had a go at implementing a plugin to rename parent packages. It adds a "Rename parent package" item to the context menu of , or can be triggered by ctrl-7.
I've not implemented the code to enable/disable the menu item based on the active selection (there's some race condition that causes the wizard to stop cancelling). If the active selection is a package with a parent package, it will select that parent and launch the rename wizard. You'll still need to select "rename subpackages" manually.
Here's the plugin code:
package name.seller.rich.packagerenamer.actions;
import org.eclipse.core.commands.AbstractHandler;
import org.eclipse.core.commands.ExecutionEvent;
import org.eclipse.core.commands.ExecutionException;
import org.eclipse.jdt.core.IJavaElement;
import org.eclipse.jdt.core.IPackageFragment;
import org.eclipse.jdt.core.IPackageFragmentRoot;
import org.eclipse.jdt.core.JavaModelException;
import org.eclipse.jdt.internal.ui.JavaPlugin;
import org.eclipse.jdt.internal.ui.actions.SelectionConverter;
import org.eclipse.jdt.ui.actions.RenameAction;
import org.eclipse.jface.viewers.IStructuredSelection;
import org.eclipse.jface.viewers.StructuredSelection;
import org.eclipse.ui.IWorkbenchPart;
import org.eclipse.ui.handlers.HandlerUtil;
public class RenameParentPackageHandler extends AbstractHandler {
    public RenameParentPackageHandler() {
    }
    public Object execute(ExecutionEvent event) throws ExecutionException {
        IWorkbenchPart activePart = HandlerUtil.getActivePart(event);
        try {
            IStructuredSelection selection = SelectionConverter
                    .getStructuredSelection(activePart);
            IPackageFragment parentPackage = getParentPackage(selection);
            if (parentPackage != null && parentPackage.exists()) {
                RenameAction action = new RenameAction(HandlerUtil
                        .getActiveSite(event));
                StructuredSelection parentSelection = new StructuredSelection(
                        parentPackage);
                action.run(parentSelection);
            }
        } catch (JavaModelException e) {
            logException(e);
        }
        return null;
    }
    private IPackageFragment getParentPackage(IStructuredSelection selection) {
        IJavaElement[] elements = SelectionConverter.getElements(selection);
        if (elements != null && elements.length > 0) {
            if (elements[0] != null && elements[0] instanceof IPackageFragment) {
                IPackageFragment fragment = (IPackageFragment) elements[0];
                String packageName = fragment.getElementName();
                int lastDotIndex = packageName.lastIndexOf(".");
                if (lastDotIndex != -1) {
                    String parentPackageName = packageName.substring(0,
                            lastDotIndex);
                    IJavaElement parent = fragment.getParent();
                    if (parent != null
                            && parent instanceof IPackageFragmentRoot) {
                        return ((IPackageFragmentRoot) parent)
                                .getPackageFragment(parentPackageName);
                    }
                }
            }
        }
        return null;
    }
    protected void logException(Exception e) {
        JavaPlugin.log(e);
    }
}
Here's the plugin.xml
<?xml version="1.0" encoding="UTF-8"?>
<?eclipse version="3.0"?>
<plugin>
   <extension
     point="org.eclipse.ui.commands">
      <command
        name="Rename parent package"
        categoryId="name.seller.rich.packagerenamer.category"
        id="name.seller.rich.packagerenamer.renameParentPackage">
      </command>
   </extension>
   <extension
     point="org.eclipse.ui.handlers">
      <handler
        commandId="name.seller.rich.packagerenamer.renameParentPackage"
        class="name.seller.rich.packagerenamer.actions.RenameParentPackageHandler">
      </handler>
   </extension>
   <extension
     point="org.eclipse.ui.bindings">
      <key
        commandId="name.seller.rich.packagerenamer.renameParentPackage"
        contextId="org.eclipse.ui.contexts.window"
        sequence="M1+7"
        schemeId="org.eclipse.ui.defaultAcceleratorConfiguration">
      </key>
   </extension>
   <extension
     point="org.eclipse.ui.menus">
      <menuContribution
        locationURI="popup:org.eclipse.ui.popup.any?after=additions">
         <command
           commandId="name.seller.rich.packagerenamer.renameParentPackage"
           mnemonic="K">
         </command>
      </menuContribution>
   </extension>
</plugin>
And the manifest:
Manifest-Version: 1.0
Bundle-ManifestVersion: 2
Bundle-Name: Classwizard
Bundle-SymbolicName: name.seller.rich.packagerenamer; singleton:=true
Bundle-Version: 1.0.0
Require-Bundle: org.eclipse.ui,
 org.eclipse.core.runtime,
 org.eclipse.jdt.core;bundle-version="3.5.0",
 org.eclipse.core.expressions;bundle-version="3.4.100",
 org.eclipse.jface.text;bundle-version="3.5.0",
 org.eclipse.jdt.ui;bundle-version="3.5.0",
 org.eclipse.ui.ide;bundle-version="3.5.0",
 org.eclipse.ui.editors;bundle-version="3.5.0",
 org.eclipse.core.resources;bundle-version="3.5.0"
Eclipse-AutoStart: true
Bundle-RequiredExecutionEnvironment: JavaSE-1.6