This answer is based on Another answer posted by Elder Geek, this just makes it easy for new users to execute
Original Work
For 17.04
Open the software and updates app and select multiverse and universe repositories

and run the following command after enabling them
sudo apt-get update
Install ubuntu-restricted-extras
sudo apt-get install ubuntu-restricted-extras
This command should do it, You'll need to use the Tab key to highlight the OK button for the mscore fonts package and hit enter to accept the agreement, How do I install the ubuntu-restricted extras package? (for more details)
You don't need to install ubuntu-restricted-extras if you've already installed media drivers while installing ubuntu
Install ffmpeg
sudo apt-get install ffmpeg ffmpegthumbnailer
These commands will install ffmpeg, after that delete all the existing thumbnails. by doing
rm -r ~/.cache/thumbnails
Change the job of creating thumbnails from Totem to ffmpeg
sudo nano /usr/share/thumbnailers/totem.thumbnailer
a text file will open up, replace all the text inside it with the following
[Thumbnailer Entry]
TryExec=ffmpegthumbnailer
Exec=ffmpegthumbnailer -s %s -i %i -o %o -c png -f -t 10
MimeType=application/mxf;application/ogg;application/ram;application/sdp;application/vnd.ms-wpl;application/vnd.rn-realmedia;application/x-extension-m4a;application/x-extension-mp4;application/x-flash-video;application/x-matroska;application/x-netshow-channel;application/x-ogg;application/x-quicktimeplayer;application/x-shorten;image/vnd.rn-realpix;image/x-pict;misc/ultravox;text/x-google-video-pointer;video/3gpp;video/dv;video/fli;video/flv;video/mp2t;video/mp4;video/mp4v-es;video/mpeg;video/msvideo;video/ogg;video/quicktime;video/vivo;video/vnd.divx;video/vnd.rn-realvideo;video/vnd.vivo;video/webm;video/x-anim;video/x-avi;video/x-flc;video/x-fli;video/x-flic;video/x-flv;video/x-m4v;video/x-matroska;video/x-mpeg;video/x-ms-asf;video/x-ms-asx;video/x-msvideo;video/x-ms-wm;video/x-ms-wmv;video/x-ms-wmx;video/x-ms-wvx;video/x-nsv;video/x-ogm+ogg;video/x-theora+ogg;video/x-totem-stream;audio/x-pn-realaudio;audio/3gpp;audio/ac3;audio/AMR;audio/AMR-WB;audio/basic;audio/midi;audio/mp2;audio/mp4;audio/mpeg;audio/ogg;audio/prs.sid;audio/vnd.rn-realaudio;audio/x-aiff;audio/x-ape;audio/x-flac;audio/x-gsm;audio/x-it;audio/x-m4a;audio/x-matroska;audio/x-mod;audio/x-mp3;audio/x-mpeg;audio/x-ms-asf;audio/x-ms-asx;audio/x-ms-wax;audio/x-ms-wma;audio/x-musepack;audio/x-pn-aiff;audio/x-pn-au;audio/x-pn-wav;audio/x-pn-windows-acm;audio/x-realaudio;audio/x-real-audio;audio/x-sbc;audio/x-speex;audio/x-tta;audio/x-wav;audio/x-wavpack;audio/x-vorbis;audio/x-vorbis+ogg;audio/x-xm;application/x-flac;
To save updated file in Nano press Ctrl + X and then type y and enter. How to edit files in a terminal with nano?
You can use other text editing apps to edit /usr/share/thumbnailers/totem.thumbnailer file if you're not comfortable using nano
and the restart nautilus
nautilus -q
Clear all the thumbnails again and check if you're problem is solved
rm -r ~/.cache/thumbnails
The command above will clear all the thumbnails again, go check them, they will not be monochromatic now'
If you're losing Mp3/flac thumbnails after doing this, then try this approach instead