It seems my notification tray problem was an unrelated bug. Now that that's sorted out, I see that update-notifier does eventually appear (minimized) when it finds that updates are ready for me, and sometimes even opens its window on the desktop. I'm not sure yet, but it might be that it's showing the window only when security updates are available.
I think this is the behavior on Unity desktops, which makes me think this whole problem is likely another example of someone applying changes to a widely used program to suit Unity, and breaking the program on other desktops in the process. (For example, bug 1186801)
It seems my notification tray problem was an unrelated bug. Now that that's sorted out, I see that update-notifier does eventually appear (minimized) when it finds that updates are ready for me, and sometimes even opens its window on the desktop. I'm not sure yet, but it might be that it's showing the window only when security updates are available.
I think this is the behavior on Unity desktops, which makes me think this whole problem is likely another example of someone applying changes to a widely used program to suit Unity, and breaking the program on other desktops in the process. (For example, bug 1186801)