Random idea: they might be using a single pixel "image" that they generate in memory, and then handing that image to their tiling routine, which duplicates and tiles it all over the massive resolutions we use today. Back in the day, using small tiling images on webpages was discouraged because slower computers/browsers would take forever to render them, even though they were simplistic in appearance.
According to the article, using a solid-colored image for the background is actually a workaround for the problem.
The fact that the symptom is a hard 30-second delay independent of processor speed, resolution, or graphics card suggests that the computer is not actually chugging through anything.
I've never used Windows 7, but does anyone know if there's any kind of... auto-pretty-ficiation stuff that it might be trying to do? Like, trying to center the image on the "most interesting" part of it or something like that?
I moved my main desktop to Win7 this last weekend, I'm going to guess it has something to do with a untested edge case in the logic that rotates wallpapers in the background.
There is a concept of themes, and part of that is rotating background images.