I had this same problem and tried a few different methods including those above and nothing worked.
I installed this plugin: http://wordpress.org/extend/plugins/simple-301-redirects/
and that seems to have done the job, although certain URL's that contained brackets - ( or ) - are still not redirecting so I think that may be what was causing the problem.
I also noticed as I was adding the URLs in to the plugin that I had a couple of errors in the list of 301's that was causing the 500 internal error, but even with these removed the other redirects didn't work (they just went to the new WP homepage instead of the new URL)
I recently added 301 redirects to a WP htaccess file that didn't contain any of these funky characters in the URLs and everything worked fine, so I'm fairly sure they are likely to be the culprit.
Hope this is of some help to other people experiencing this annoying issue.