The thumbnail threshold only affects the size of thumbnails you upload from the time you change it forward. it does not affect thumbnail size of older photos.
If you want to change the thumbnail size and rebuild all the thumbnails in the gallery. You would set the thumbnail size you want in upload options in admin and save. You would then go to admin => scan database and check rebuild all thumbs and hit submit. You then wait until it reprocesses all the images and the thumbnails will be the new size you set.