Some people are reporting success by simply wiping data and cache first, then flashing the ROM, wiping cache again, then flashing the Gapps package. Thread on the CM forums here (from CM 6.1.1, don't know if it's a related or similar problem, though).
The flash might not work on a 2.x release of CWM. You can get 18.104.22.168 here, but I don't know how stable it is right now. The filesystem changed to
ext4 in Gingerbread and I know the 2.x releases aren't really supported on other devices. They also changed from one update scripting language to another, which I think is related. It creates generally weird behavior from what I've read...
Edit: Also looks like you can get CWM 22.214.171.124 from the CyanogenMod Forums now.
Some relevant discussion can be found on XDA here (from the Desire HD section).
Edit: Since Bryan noted that this solved it for him in the comments: It's also possible to simply push the apps manually onto the system partition. The safest way is probably to boot into recovery, then just mount
/system as rw and
adb push the .apk files to
/system/app. You probably could do it from a regular boot (not in recovery) but it might cause some weird behavior (and I have not personally tried this).