After much flailing, including re-installing hplip and xsane, and doing sudo
ln -s /usr/lib/libhpmud.so.0 libhpmud.soI finally got brave and simply moved ~/.sane/xsane to ~/.sane/xsane.old, then started xsane and it worked.
After the fact, I figured out that the problem started when I clicked on the preview pane in xsane and set the size of the area I was scanning to 0. The message wasn't very helpful. (I figured it out by diff'ing the xsane.conf that worked with the one in xsane.old.)
In addition, hp-check reports there's no plug-in installed for my printer, even though everything seems to be working. Go figure.
All this under Ubuntu 9.04 using an HP CM1312nfi MFP.