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
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.