This has been showing up more often recently. It used to mean that there was a corruption of some form either in the file or its header, and your OSX rejected it. Now it also shows up as a response to your initial request to download. So, to be constructive, the advice has to fall into two parts. It seems that some prospective hosts are not providing a valid source for the files requested. No matter how many times you try to connect, you will always get that message instantly and without going through the normal handshaking protocol to connect. You cannot change that reality so block that host and exclude it from future searches. This will save you much time and frustration as you slowly exclude the unco-operative hits from your seach results.

As to the appearance of this message (a) during or (b) at the end of the download?

(a) assuming that you have kept the original hit in your search box, kill the download and restart the download from the original source. This will often clear the blockage. If it does not, repeat the search using the same typography as for the failed download. By re-establishing the connection, you can often restart the download without further problem.

(b) if you drop into the incomplete folder, you should find a version of the downloaded MP3. If that plays properly and it is actually complete, drag it into Library. If it does not play, you can try killing the download and restarting it from the original source but, since your incomplete file is apparently defective there is little hope of rescuing the situation. Sadly, you will have to find an alternative source and download from it.

I am not sure what you mean by using "software update" but, at present, whatever it is would be unlikely to help you. However, the reverse may provide a respite while any bugs in the latest upgrade are worked out. You can actually download older versions and, if absolutely every host you are trying is throwing up this message, this may be the best solution for you at this time.