I don't think that solution is so elegant. It seems to me that the use of exceptions is gratuitous. Here's how I would have written something like this in ML:

fun intf base next 0 = base
  | intf base next n = next (n, (intf base next (n-1)));
val iota = intf [0] (op ::);

local
      val append = foldl (op @) []
      fun repeat x = intf [] (fn (_,ls) => x::ls)
      fun rep2each x n ls = map (fn e => (repeat x n) @ e) ls
in
  fun change nil 0 = [[]]
    | change nil _ = []
    | change (c::cs) x =
         append (map (fn n => rep2each c n (change cs (x - n*c)))
                     (iota (x div c)))
end;
[download]

Unlike the code in the original post, this one generates all the solutions instead of only the first one. One interesting approach if you only need one solution is to define a datatype that represents a possibly-absent solution:

  datatype 'a option = Solution of 'a | Nothing;
[download]

Then you need a couple of utility functions for dealing with it:

  fun sflat ls = foldr (fn (Solution x, _) => Solution x
                         | (Nothing,v) => v) 
                       Nothing ls;
  fun smap _ Nothing = Nothing | smap f (Solution x) = Solution (f x)
[download]

sflat takes a list of possibly-missing values and returns the first one that isn't missing. smap takes a function and applies it to a (possibly missing) value. Then you can implement change like this:

local
  fun repeat x = intf [] (fn (_,ls) => x::ls)
in
  fun change1 nil 0 = Solution []
    | change1 nil _ = Nothing
    | change1 (c::cs) x =
         sflat (map (fn n => smap (fn x => (repeat c n) @ x) (change1 
+cs (x - n*c)))
                     (iota (x div c)))
end;
[download]

Now change1 [5,1] 12 returns Solution [5,5,1,1] and change1 [3,8] 10 returns Nothing. Haskell has this Solution / Nothing type built in. Also, in Haskell, whenver you think of this "option" type, you immediately start thinking about monads. I think use of monads would probably simplify this version of the function considerably---at the expense of introducing monads---but that's a post for another day. (Short summary: monads abstract out the similarities between all three of these solutions, replacing the exceptions, the list values, and the option type values with a single abstraction.)

If all you want is to count the solutions, it's simpler, because you can get rid of all of ML's clumsy value construction syntax:

local val addup = foldr (fn (a,b) => a+b) 0
in
  fun countchange nil 0 = 1
    | countchange nil _ = 0
    | countchange (c::cs) x =
         addup (map (fn n => countchange cs (x - n*c))
                    (iota (x div c)))
end;
[download]

ML has a TCL look to it...

I don't think anyone has ever said that ML's syntax was one of its better points.