Version 1 - Replace in modules/imagemagick/classes/ImageMagickToolkit.class:

/* Don't enlarge images for a thumbnail */
 	    if ($width > $parameters[0] || $height > $parameters[0]) {
 		$this->_addResizeParam($transform, $parameters[0]);
 		list ($width, $height) =
 		    GalleryUtilities::scaleDimensionsToFit($width, $height, $parameters[0]);
 	    }

with:

/* Create the thumbnail with fixed width */
	    $aspect = $height / $width;
	    $targetWidth = $parameters[0];
	    $height = round($targetWidth * $aspect);
	    $width = $parameters[0];
	    $this->_addResizeParam($transform, $width, $height);

Version 2 - replace in modules/imagemagick/classes/ImageMagickToolkit.class:

/* Don't enlarge images for a thumbnail */
 	    if ($width > $parameters[0] || $height > $parameters[0]) {
 		$this->_addResizeParam($transform, $parameters[0]);
 		list ($width, $height) =
 		    GalleryUtilities::scaleDimensionsToFit($width, $height, $parameters[0]);
 	    }

with:

/* Create the thumbnail with fixed width */
            list ($width, $height) =
                GalleryUtilities::scaleThumbnailToFit($width, $height, $parameters[0]);
            $this->_addResizeParam($transform, $width, $height);

and add to modules/core/classes/GalleryUtilities.class:

function scaleThumbnailToFit($width, $height, $targetWidth, $targetHeight=null) {
 	$aspect = $height / $width;
 	$width = $targetWidth;
 	$height = round($targetWidth * $aspect);
 	return array($width, $height);
     }