Check out the admin/common/properties.php file. You can add new sizes in there. Once you update this file, you'll have to re-process your images so the new sizes are created. You can do that by updating the watermark settings (even if you just have a blank watermark). The gallery designs are designed to use the image sizes as specified, so you'll have to update the gallery PHP code if you want them to use a different size.
-justin