If you have FTP access to edit your .htaccess file, you can try to do something like the third suggestion found here: http://crosstown.coolestguidesontheplanet.com/web-host/23-redirecting-a-web-folder-directory-to-another-in-htaccess
RewriteRule ^subdirectory/(.*)$ /anotherdirectory/$1 [R=301,NC,L]
I think in your case the code would look something like:
RewriteRule ^blog/(.*)$ /newname/$1 [R=301,NC,L]
Although your example seems to be using generic directory names, so replace "blog" and "newname" with whatever you're actual directory names are.
If you don't have FTP access, try using one of the htaccess plugins available. http://wordpress.org/plugins/search.php?q=htaccess
There are several 301 redirect plugins out there as well, but I think most require you to specify each individual page redirect. With hundreds of posts, this would get extremely time consuming to set up.
If you're not too comfortable with editing the htaccess file, there is a bulk uploader add on for the Simple 301 Redirects plugin. I haven't personally used the bulk uploader add on, but Simple 301 Redirects is fairly simple to use - I would imagine that the uploader is as well.