Comment 33 for bug 364127

To answer my own question: I simply downgraded to the Intrepid version of the package:
http://archive.ubuntu.com/ubuntu/pool/main/h/hotkey-setup/hotkey-setup_0.1-23ubuntu7_i386.deb

The OSD notification now works nicely, and nothing else seems to have been broken by this downgrade. As expected, the volume is now "double stepping", but I can live with that.