Problems Redirecting Old URLs to New Ones [WordPress 3.4.2]

I posted this elsewhere and didn’t get any help. Here’s the problem:

A few years ago this was the permalink structure I had for my blog:

/%year%/%category%/%postname%.html

I changed these permalinks last year to this:

/%category%/%postname%/%post_id%/

A plugin that goes by the name “Permalinks Redirect” was used, and it worked pretty well to permanently redirect older URLs to newer ones. However, after a recent WordPress update to 3.4.1 version, I noticed the older permalinks are no longer redirecting.

The problem is not with the plugin — I have spent 2 days dabbling with every redirect plugin I could find. After a bit of Googling, I figured out the problem is with WordPress 3.4, and a bug has been already submitted.

Link: http://wordpress.org/support/topic/changing-permalinks-not-redirect-the-old-to-the-new#post-2913004

All the older URLs are throwing out 404 errors, which is frustrating. I already use a plugin that redirects 404 pages to other ones but, as expected, it sometimes redirects to irrelevant posts. Is there anything else I could do here?