Open System->Preferences->Compiz Settings Manager
Go to the Animations plugin:
Under the Open Animation tab, remove the "Notification" type from the second Fade so that it reads:
(type=Tooltip | Utility) & !(name=compiz)
Do the same with Close Animation.
Then disable/re-enable the Animations plugin.
Notifications now fade in smoothly and out.
Ken: are there any upstream patches or patches from Ubuntu to make this suck less? I'm beginning to suspect that it's more than a configuration problem....