You might have to get your hands dirty and do manual red-eye removal.
There are various methods depending on the editor you're using.
One of the easiest manual methods is just desaturating the objectionable color with the appropriate tool.
Paint Shop Pro has really good red-eye correction capabilities, as does Photoshop Elements, but I'm sure that you can find a program that will let you address the problem for a lot less money than they cost. But, you may have to do it manually for good results.
Another good fix is to avoid the problem in the first place and get an external flash with bounce capabilities or just make a diffuser for it. A flash bracket that holds the flash up high and off to the side will lessen or eliminate the problem also.