If you add the new picture but with the same name, you need to remove the thumbnails. You can do it e.g. via media manager or FTP, just remove the thumbs in thumbs folder (for the specifed category) or you can use the recreate function, see image (Admin - Phoca Gallery - Images list).
This function will delete the image thumbnails and create new (and if new original image is uploaded, the new thumbnail will be created from new image.
Jan