I had the same problem. Yes: HAD!  ::)

My solution was: i put an extra slash in the code within the article, before the first folder.
So...
NOT: {gallery}2009/test{/gallery}
BUT: {gallery}/2009/test{/gallery}

then it worked for me.

Another issue i had: for testing purposes, put the thumbnail-cache to 0 (zero) because otherwise your thumbs wont change (if you play with the size for a better layout) if you want smaller or bigger thumbs.