dhenry:
so I'll just try some bigger caps than so far.
It is not terribly critical. I usually use whatever I have and I tend to stay small. But starting with what the datasheet suggests helps. And for highspeed circuits, starting with a ceramic disc (monolithic or otherwise) helps as well. I usually avoid tantalum as they tend to fail short. 10nf - 110nf is fairly common.
Tantalum are rubbish for decoupling. So are most electrolytics.
Here's Atmel's advice on decoupling capacitors: http://www.atmel.com/Images/doc0484.pdf