The picture on his site makes them look a little small for the pieces. I was wondering if this is actually the case.

(I was thinking about ordering an extra puzzle to make a 20-colored version, using his stickers.)

I used Oliver's stickers on the MF8 coloured Master Kilominx that I dyed black. They are much smaller than the pieces.

If you aren't happy with the fit of stickers Olivér does template redesigns for a very reasonable price. Not only that, if you help Olivér make a better template for a puzzle, everyone else that orders that template benefits too.