When you right-clicked on the project in the project navigator did you click rename in the main dropdown, or did you click on "Rename Application Package" within the android tools sub-menu? You should be using the later option.
Also verify that the AndroidManifest.xml Label field is correct, or if it is pointing to a value in strings.xml within res/values verify that the application name is correct.