Changing the package name is a pain in the ass. It looks like different methods work for different people. My solution is quick and error free. Looks like no cleaning or resetting eclipse is needed.
Right-click on the package name then Refractor > Rename.
Right-click on the project name Android tools > Rename Application Package.
Manually set the package names in the Manifest that have not been changed by the previous steps.