Oh, boy. Have you any experience in MySQL and databases?
If not, then check with the following sites to download and install Batch Categories. It's not really a plugin, but could be, so read through all the documentation to install it. Use this to go through your entire site and "move" the posts into the new category.
If you can't find it there, contact me and I'll try to get a working copy to you.
If you are familiar with MySQL, you have to change the category links in the following table,
wp_post2cat, for every post in which you want to have in the "new" category.
Later: Oh, you only are missing two posts. Then skip all of this (left for reference) and download the Enhanced Post View plugin from http://www.coldforged.com/ and that will allow you to sort your posts in a way to track down the two missing posts and change their category reference. MUCH EASIER.