Well, when running the command - sudo update-apt-xapian-index on Lubuntu 12.04 to make Synaptic (it rocks) list packages from 3rd party repos I got the following error:
sudo: update-apt-xapian-index: command not found - Lubuntu 12.04
The reason is quite simple - the package apt-xapian-index turned out to be not install (nice). Which is why all you have to do is to install it:
sudo apt-get install apt-xapian-index
And then rebuild the xapian index again (run the initial command). That's it. Synaptic is now fully usable.