Here's a nice YouTube video of an NXT-based coin sorter. While it certainly doesn't compete with CoinStar yet as far as speed goes, it shows not only an interesting problem and solution... but a whole lot of wonderful mechanisms, as well as a pretty well done video explanation:
I can't quite see how it only grabs one coin, but the two-stage grab-&-dump mechanism driven by a single motor is one of my favorite techniques. Very often, you do not need more motors, just a clever mechanical solution to get multiple motions out of a single motor, as kevquest does here. The actual sorting mechanism is also very well done, and adaptable - by adjusting those limiting elements, a lot of different sized objects could be sorted. Yet another important point is the sorting tray - I've seen a lot of folks get hung up on linear motion, and go through a lot of exertion to try to get it, when many times it's simply not needed - like here, where a carrousel style system is perfectly sufficient. About the only thing I don't quite understand is the reseting pattern (I think there might be quicker ways to do it) and the speed (could it be speeded up? If not this mechanism, I'll bet there are faster mechanisms that might work). Again, a nifty creation, and a nice YouTube documentation. Take a look!