Says Eimi Metamorphoumai:

Interestingly, that only gives you the smallest number of coins for certain combinations of denominations.

I looked into this in some detail a while back also. As you point out, the greedy change algorithm for the US (1, 5, 10, 25) system always delivers the minimum possible number of coins for any amount, but this is a property of the particular denominations used. Clearly, a system with coins of size 1, 10, and 11 does not have this property, since the greedy algorithm gives change for 20 cents by starting with an 11-cent coin, and then delivers nine pennies.

When I realized this I started to look around to see if there were any widely-used coinage systems that did not have the greedy property. I was pleased to discover one: the pre-decimalization currency of the United Kingdom included the following coins:

    half-crown  =  30 pence
    florin      =  24 pence
    shilling    =  12 pence
    sixpence    =   6 pence

When changing four shillings = 48 pence, the greedy algorithm delivers a half-crown, a shilling, and a sixpence, but the optimal solution delivers two florins.