Have you checked the image size ? Not what you see in the web site.
When images are shown on web site, it will be resized using CSS to fit in site lay out properly. So after you regenerate the image, clear cache, access image directly to see the image size.
Now you will need to update web site layout (CSS and tpl) files, so that web site work with new thumbnail size.
Bookmarks