I have found a very simple solution to this problem.
After a single change, the above folder now looks like this when set to 200% icon zoom level:

It was as simple as changing the "thumbnail-size" value in "dconf-editor" for nautilus to a larger value.
To apply the change, make sure "dconf-editor" is installed in your system by typing the following into a terminal:
sudo apt-get install dconf-editor
After installing, type Alt - F2 to pull up the command dialogue, and type "dconf-editor" to search for it and click on it.
Once you have "dconf-editor" open, navigate to the following location in the left pane:
org > gnome > nautilus > icon-view
See this example image for the location:

The value that needs changed is the "thumbnail-size" value. I changed it from a default of 64 to 128. Depending on your display resolution, you may need to change it to a different value to make things look exactly the way you want. Smaller displays might need a value larger than 64, but 128 might be to large, so try something like 96.
Once that value is changed, exit "dconf-editor". Now the thumbnail cache needs to be cleared to allow that changes to take effect.
First close all Nautilus windows, then type the following code in a terminal (each line is a separate command).
nautilus -q
sudo rm -r ~/.cache/thumbnails/
The first command makes sure Nautilus is closed, and the second clears your thumbnail cache.
Note that this does not affect file or folder icons. Those will still appear to be smaller than the picture and video icons generated by Nautilus (or more correctly generated by ffmpegthumbnailer). This is still a huge improvement for thumbnails in Nautilus even with this shortcoming.
This fix worked on Ubuntu 14.04.1.
sudo
will be necessary in any normal case, and it is always better to avoid it if possible. – Arild Mar 12 '15 at 21:17Hopefully they keep it that way.
– ChameleonScales Mar 13 '23 at 22:08