Comment 2 for bug 1579834

I too suffered this exact same issue that Carlo Vanini lists here. It was my work with him and another developer of muon package manager that helped him find this issue. Between three of us we were able to narrow the issue in muon down to this issue. This issue occurred with me when I ran Kubuntu 16.04 LTS in VirtualBox as well as on bare metal. My system is a Dell Inspiron N5010 laptop with 8G of ram, 640G hard drive, Intel i5 M460 processor, and Broadcom wireless. I used both muon and synaptic in 16.04 LTS to check this issue. The only place I found the issue was within muon. Synaptic did NOT have the search issues that muon did. I do hope this issue gets resolved as I prefer muon as it's a native KDE application and has some features that synaptic does not have (like being able to remove unnecessary packages without resorting to the CLI).