The CSS margins/paddings are actually too little, about 5px. You obviously have more than 5px to deal with, both of you.

So, I will repeat once more, that you need to add a smaller height value. DO NOT WORRY, it will not make your thumbs shorter, it will just decrease the inbetween vertical space.

If you've already set a "master" width and height value, use the custom options to set unique width/height per gallery if you wish. For that, please read the instructions in the plugin's parameters page.

You need to wait for the cache to reload (default is 120 minutes, change it to 0 for near-instant changes).  ;)

Clear Joomla's cache too if you have it enabled.

Justify cannot align the gallery in the middle, try increasing the thumb width to fill all available space...  ;)