When can a greedy algorithm solve the coin change problem?
A coin system is canonical if the number of coins given in change by the greedy algorithm is optimal for all amounts. 

The paper D. Pearson. A Polynomial-time Algorithm for the Change-Making Problem. Operations Reseach Letters, 33(3):231-234, 2005 offers an $O(n^3)$ algorithm for deciding whether a coin system is canonical, where $n$ is the number of different kinds of coins. From the abstract:


  We then derive a set of $O(n^2)$ possible values which must contain the smallest counterexample. Each can be tested with $O(n)$ arithmetic operations, giving us an $O(n^3)$ algorithm.


The paper is quite short.

For a non-canonical coin system, there is an amount $c$ for which the greedy algorithm produces a suboptimal number of coins; $c$ is called a counterexample.  A coin system is tight if its smallest counterexample is larger than the largest single coin.

The paper Canonical Coin Systems for Change-Making
Problems provides necessary and sufficient conditions for coin systems of up to five coins to be canonical, and an $O(n^2)$ algorithm for deciding whether a tight coin system of $n$ coins is canonical.

There is also some discussion in this se.math question.