Hello!
I apologize for effectively reviving this thread, but I once had the same problem and you are so far the only person online to show that I was not alone. There is an EXTREMELY easy fix for this, however I did not know at the time and actually ended up reinstalling WIndows out of fear!
The fix is:
1) Open up Command Prompt and run as Administrator. (Search "cmd" in the Start Menu, right-click the "Command Prompt" search result, and click "Run as Administrator")
2) Type "sfc /scannow" and press ENTER.
3) Once the scanning is complete, restart your computer.
That's it! It worked for me!
I tried to change the startup sound again a few times after this, but every single time this same issue happened. (The "sfc /scannow" command fixed this every time.) I actually figured out curious thing, which is that this issue only happened to my user account and the user accounts that were not logged into my PC at the time. I had another user account logged in at the time that had a 100% fine display of icons, and apparently means that Startup Sound Changer have something to do with this. I tried one last attempt, which I thought would, and almost, worked until I gave up. I logged every single user in at the same time, then fired up Startup Sound Changer and changed it. I immediately got a Blue Screen of Death.
I gave up after this, but you or anyone who gets this problem should feel free to play-around with my "almost-solution" to Startup Sound Changer constantly changing the icons on the desktop even after restoring them. I really do hope that you were somehow able to solve this without having to tediously reinstall Windows like I ended up doing, or that this post helps you in some way. Hopefully in the end you can somehow get the new startup sound to work!