I hardly did anything. I just ripped open the Gmail APK and found the offending icon. I'm not even sure why it's there, but I replaced it with its proper icon, and then just de-crapified the GApps package of stuff I didn't really need. If you still want the full GApps and the fixed Gmail APK, just take the GMail apk out of my custom package, and replace the the standard GApps package's GMail.apk with it.
I have the same funky looking gmail notification icon as you but i like the functionality of the current gmail app. Is there anyway i can pull the traditional icon out and paste it over the current crappy looking icon i have now??