I'm using Windows 7, 32-bit, and the following works for me and is reproducible.
Right-click on the desktop. From the drop-down menu select "Personalize."
From the offering of "Themes" select "Windows 7 Basic"
After the newly selected theme is displayed you may close the "Personalization" window.
Now, arrange all of the icons where you want them. Re-boot.
When the desktop comes up all of the icons should be where you left them.
Now you can change to a different theme. Rt-click the desktop, select personalize and then pick a theme. I use Landscapes and all of my icons stay where they should.
One obvious shortcoming is that every newly added icon would require this procedure.