The windows servicing devs were able to repro the problem and understand the cause.
They are working on a plan to fix this without risking regression or disruption to those who installed the KB successfully, i.e. those with existing fully patched systems who updated April 14th (Patch Tuesday). That is, of course, the majority of Win7 systems out there. I got caught, like you, trying to clean install from media after April 14th.
Some of the patch juggling and acrobatics described in various posts in this thread may be potential work arounds as they change the sequence that the system sees these updates. I'm particularly optimistic about one. I'll try and see how it goes when I get home (late night).
I'll update when there's something definite about an official fix (no acrobatics required), though you may see it first as just a new update to install. I don't represent or work for the Windows servicing team. I just got bit by the same bug as all of you and am trying to help.
Thanks,
David