If you guys find this issue, there is an easy way to solve it. It works as follows:
1/ Go to \\Users\"username"\Documents\Native Instruments
2/ Find the folder named as the old version of Traktor, for example Traktor 3.XX
3/ Inside that folder, is a subfolder called Coverart. Copy the contents of that folder.
4/ Go back to \\Users\"username"\Documents\Native Instruments
5/ Find the folder named as the new version of Traktor, for example Traktor 4.XX
6/ Inside that folder, is a subfolder called Coverart. Go inside it and paste what you copied in step 3.
Done: All your art is there now. :)