I really have no idea. I don't use Ubuntu or anything debian-based, and if I did, I would probably use the command-line search option which I am sure exists.
The fact that apparently Synaptic does not know how to natively update its own search index is actually quite unimpressive, in a fairly frightening manner. I suggest you report it as an upstream bug, filed to the "what weren't you thinking" department.