The [algorithms book by Kleinberg and Tardos][1] 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). 


  [1]: http://www.aw-bc.com/info/kleinberg/