WeWhen we started recycling more aggressively at my workplace a few years ago, we found that (a) most people want to do the right thing and (b) people don't want to have to work at it. The recycling bins in the kitchen and by exits are a fine start, but what made the difference for us was giving everybody a recycling bin alongside his personal trash bin. (We don't have to separate materials, though, and it sounds like you do.)
To figure out where to place which recycling bins, start by looking at what is getting tossed into the trash where. Are people mostly tossing paper at their desks and next to the printer? Put paper bins there. Are people tossing drink cans in meeting rooms? Put aliminumaluminum bins there. Analyze your current user behaviors and go from there.
For any new program that asks people to change their behavior, you'll likely get better results if you react to the current behavior. Tweaking which bin an employee tosses something in is easier than getting that person to walk to a different part of the office to drop it into a bin there.
As for shared rewards, the challenge there is always the tragedy of the commons and the resentment it can produce when some people are dillegentdilligent, some are slackers, and everybody gets the same outcome.