Hmmm interesting UX question. I usually assume UX will be about websites... but this is completely valid, too!
Color Code It
You guys had it right when you were color coding things. My suggestion would be to make the trash can red. Of course, red means "stop" or "danger" to us so you'll [hopefully] find that people will hesitate before using the red bin.
Don't Make Them Think
This small hesitation is your one chance to get them to READ. Otherwise, people will never read any sign you put up. (We hate reading, really--I'm surprised people read my long-winded answers!)
Symbols are your Friends
Remember, no one reads... but their subconscious will translate the symbol into meaning. On the red trash can, place a white piece of paper (printer paper, I'm assuming since you probably have that there handy) with a green or black arrow pointing towards the recycling bin.
Wait... what are you recycling? Well, try out FontAwesome (or icons on the interwebs) to make a picture of various things you want them to recycle in the specified bin. Plastic? Find a plastic bottle icon. Aluminum? Find an icon of a can.
Important: Place small text below the images to explain what the image means if the person can't figure it out, but the image should be the main attraction.
You can print this out and put this on the recycling bin... which by the way, should be green!
Whoa, red and green, hold on!
Up to 10% of the population is color blind, and some people have a hard time differentiating between red and green. That makes this whole color coding thing harder for them and you'll see less success with them until they have read and memorized the symbols / locations of the bins.
Chicken or the Egg?
Experiment with putting the regular, red trash bin on the right and the recycling on the left, and vice versa. There are a lot more right-handed users than left-handed, so I imagine more people would go to use the right bin first--so, that could be your red trash can. (Because the red trash can is what makes them stop and think.) This may not work as well though, so switch it up and see if the other way works better.
Because the current "labels" of which trash can is which is on the door of the cabinet, people are not able to see the label when they are using the trash bins. This causes them to use either or and is another reason you are experiencing this issue. They need to be able to see the label clearly when they are making the decision on which bin to use.
Phew, that was fun! Hope that helps. :)