I'm running Synaptic under Easy Debian. It's a brand new install. It seems that if you search for something it'll think long and hard about it before responding. After my post I waited about 3-4 more minutes (at 100% CPU) and I got the results of the search.

The only way around this is to browse for the items you need rather than searching.