The same thing is happening with the new Gmail as happened with Voice Search. This again?
adb shell rm /system/app/Gmail.apk
adb uninstall com.google.android.Gmail
I installed it simply by going to the market and updating to the new version. I know I have it installed correctly as it popped up a "What's New" dialog on first run.
I have a HTC Magic 32A with CM6.
You need to install the Google apps for Cyanogen. Download the signed zip from the link below, there is one for the ROM (you don't need) and one for Google apps. All you have to do is install it from recovery just as you would a custom ROM. Should solve your problems...
UPDATE: The link above is for the HTC Magic. The one below is for Nexus One. Not sure if there is a difference in the zips, but just in case use this one for Nexus One.