The algorithms book by Kleinberg and Tardos has a number of such examples, including the baseball elimination one. It has a flight scheduling example that I've used in class - the graph cut example is also easy to explain. The problems have many more.
The examples work, in that students tend to have 'aha' moments (or so they tell me).
