There is probably something in your backup or possibly an extension (maybe wget.tcz? - just a guess) that is interfering with the search functions.
Under my normal TinyCore/MicroCore (3.6) setup, I get the same (lack of) results as coreplayer reports.
If I boot TinyCore base norestore, I get the (good) results Juanito reports (it doesn't just search for extensions names (which would not be terribly useful), but apparently searches the .info files' contents (which very useful, though occasionally frustrating)).
If you need wireless, booting with base norestore might not be very helpful.
At a glance, /usr/bin/provides.sh and /usr/bin/search.sh do not seem to be the issue.
I haven't debugged further than that and probably won't have time to today.
Edit: wget.tcz is not the issue. While I sometimes need it, I do not load it by default and it was -not- loaded when I tested earlier.
20110609 1206