iMac 2009 Mac OSX 10.7.5 Mem 16 GB 1067 MHz DDR3
There are a couple of things to look at here.
The first thing is to ctrl+click on All My Files in the sidebar in Finder and select Show Search Criteria. Make sure that All My Files is selected and remove any bizarre criteria that may have gotten in there. The default selection criteria are:

Any of the following are true
-- Kind is Document

Some apps may install their own search criteria. For example, I also have &quot;Kind is Other com.microsoft.&quot; due to running Microsoft Remote Desktop and how it stores RDP connection files.
If fixing your search criteria doesn't restore your results, you may want for reset your Finder preferences by deleting a couple of .plist files:

com.apple.finder.plist
com.apple.sidebarlists.plist

You'll find those by choosing 'Go' from the Finder menu, pressing option and then selecting 'Library' and navigating into the Preferences folder. Delete these files and then 'Force Quit…' Finder from the Apple menu or restart your system. That should get things back to order for you.