The changes you make in Settings -> Media only affect images going forward, since the images themselves are stored on the server. That means you'll need to take another approach to get the thumbnails to regenerate.
First, to avoid the cropping, go to Settings -> Media and confirm that you have unchecked "Crop thumbnail to exact dimensions (normally thumbnails are proportional)" and save your changes.
I think WordPress will just regenerate a thumbnail if you delete it, but you should test this on a single image to make sure I'm right before you do a bunch! If you want to try this, you need to delete the old thumbnail you want to have WordPress regenerate from the server. Use whatever file manager or FTP client you have set up for your server. Unless you changed the default file path, the thumbnails will be in /home/<your user name>/public_html/wp-content/uploads/<the year>/<the month>/<the file name> where the file name includes the size of the image, the smallest one being the thumbnail in most cases. Locate the thumbnail for the image you want to have regenerated based on the file url in the media library.
Delete the thumbnail, browse to the page where the thumbnail should display in the blog, and see if WordPress regenerated it. If it worked, you can do the rest the same way.
If you need to regenerate a lot of thumbnails, you might want to take a look at the Regenerate Thumbnails plug-in.
The best thing to do is make all the changes to future images before you save them, or even before you upload them.