Chris,
I made the same 5D > 5DII switch about 4 months ago and have noticed a big difference. Two things:
1. I may have simply had a lot of dirt in my old 5D from so much outdoor use. Manual cleaning just gave it a clean slate for other dust inside the box. The newer 5DII just doesn't have that much use yet (1400 images) and hence not much dust in the box. Could be why I perceive mine to be so much better...
2. I configured my 5D to clean when I turn it on and off, not just when turned off. Shutter is obviously off in between shoots, but I wonder if dust lands on the shutter while yours is off laying around, then opening the shutter blows it around right onto the sensor. Perhaps by cleaning when it is turned on, some of the ultrasonic energy is transferred to the shutter, in effect knocking it clean as well and hence less dust falling on the sensor when it opens.
Dave