Have you tried uploading the photos again? My [limited] understanding is that wp is creating the thumbnails at the time you upload the photos.
Another option might be to look in the media.php file and see if there is a setting there to display at a different size.
The only problem with this would be if you are making the thumbnails larger than they were — resulting in pixelated images.
If I have galleries full of images, I don’t want to have to re-upload all of them if I decide to change my theme (or just want to change the thumbnail size). When the thumbnail size setting is changed, it should have an effect on all existing thumbnails, right?
I have developed a new plugin that resolves this issue and provides a number of other enhancements to the WordPress 2.5 gallery – lightbox/thickbox/etc., JPEG quality, custom image sizes, and much more. PhotoJAR: Base
