Norcross's example above is right on, but I needed the possibility of internationalization. If I had the reputation, this would be a comment under Norcross's answer, but since I don't, i'll just put the modified code here. 'i18n_context' is an arbitrary namespace for the translation context, this could be the name of your plugin or theme for example.
function change_post_menu_label() {
global $menu;
global $submenu;
$menu[5][0] = __('Contacts', 'i18n_context');
$submenu['edit.php'][5][0] = __('Contacts', 'i18n_context');
$submenu['edit.php'][10][0] = __('Add Contacts', 'i18n_context');
$submenu['edit.php'][15][0] = __('Status', 'i18n_context'); // Change name for categories
$submenu['edit.php'][16][0] = __('Labels', 'i18n_context'); // Change name for tags
echo '';
}
function change_post_object_label() {
global $wp_post_types;
$labels = &$wp_post_types['post']->labels;
$labels->name = __('Contacts', 'i18n_context');
$labels->singular_name = __('Contact', 'i18n_context');
$labels->add_new = __('Add Contact', 'i18n_context');
$labels->add_new_item = __('Add Contact', 'i18n_context');
$labels->edit_item = __('Edit Contacts', 'i18n_context');
$labels->new_item = __('Contact', 'i18n_context');
$labels->view_item = __('View Contact', 'i18n_context');
$labels->search_items = __('Search Contacts', 'i18n_context');
$labels->not_found = __('No Contacts found', 'i18n_context');
$labels->not_found_in_trash = __('No Contacts found in Trash', 'i18n_context');
}
add_action( 'init', 'change_post_object_label' );
add_action( 'admin_menu', 'change_post_menu_label' );