Taken from this Stack Exchange Thread: http://wordpress.stackexchange.com/questions/1037/renaming-custom-post-types-and-taxonomies
SQL query for renaming the posts:
UPDATE `wp_posts` SET `post_type` = '<new post type name>' WHERE `post_type` = '<old post type name>';
SQL query for renaming taxonomy:
UPDATE `wp_term_taxonomy` SET `taxonomy` = '<new taxonomy name>' WHERE `taxonomy` = '<old taxonomy name>';
That should take care of all of the database areas. Just remember to match the new names in the code where the post types or taxonomies are registered. As far as I know, this is not handled in any plugins yet.