Did either of you have to reinstall in Leopard to get these menu items showing?
No, Just go into the Preferences in each NUD and NC and toggle the check mark for the QD or QC icon to display in the menubar.
HOWEVER, they are not in the menu bar when you start up or re-boot. They need to be reactivated using this procedure each day. But, like I said Quick Day shows up but does not work. Quick Contact is operational though.
Also, want to note I am running on a PPC 1.67 MHZ PowerBook platform
YMMV.