From WP-Admin, click Gallery, then Options, then on the Thumbnails tab. Change the dimensions to what you want and click “Save Changes”.
Now, you have to do this for each gallery:
Click Manage Gallery (on the left), click on the title of a gallery, check the checkbox at the top of the images (which will check all images), then from the dropdown that reads “no action”, choose “Create New Thumbnails”, and then click “Apply” (just to the right of the dropdown).
The gallery edit page will refresh with a progress bar at the top… Let the progress bar get to 100% before you navigate away (not sure if this is required, but best to watch it).