Go to Applications/Utilities and open Console.
Note the time and then try doing "All My Files". After the beach ball stops, go to Console and post the Console report from the time you did the "Add My Files". Please do not post the entire log. If you want to post a screen shot, use command - shift -4 and then select the requested information.
That's what I got:
18.03.13 18:30:37,462 com.apple.security.pboxd: Bug: 12D78: liblaunch.dylib + 23849 [2F71CAF8-6524-329E-AC56-C506658B4C0C]: 0x25
18.03.13 18:30:37,498 com.apple.security.pboxd: CGSGetWindowTags: Invalid window 0x23e6
18.03.13 18:30:37,499 com.apple.security.pboxd: kCGErrorFailure: CGSSetHideOnDeact: error getting window tags
18.03.13 18:30:37,676 com.apple.security.pboxd: CGSCopyWindowColorSpace: Invalid window 0x23e6
18.03.13 18:31:09,501 com.apple.security.pboxd: CGSReleaseWindow: Invalid window 9190
18.03.13 18:31:09,501 com.apple.security.pboxd: _NXTermWindow: error releasing window (1000)
Any idea what it means?
I'm not very good at deciphering error logs. I suggest that tomorrow you make a new post to bump this back to the top of the list in hope that someone smarter than me can make sense of it. Some other troubleshooting you can try.
Do a backup, using either Time Machine or a cloning program, to ensure files/data can be recovered. Two backups are better than one.
Run Disk Utility/Repair Permissions. Run until it reports no errors. If there is a recurring error, see the article on what permission errors can be ignored.
Try setting up another admin user account to see if the same problem continues. If Back-to-My Mac is selected in System Preferences, the Guest account will not work. The intent is to see if it is specific to one account or a system wide problem. This account can be deleted later.
If the problem is still there, try booting into the Safe Mode. Shut down the computer and then power it back up. Immediately after hearing the startup chime, hold down the shift key and continue to hold it until the gray Apple icon and a progress bar appear. The boot up is significantly slower than normal. This will reset some caches, forces a directory check, and disables all startup and login items, among other things. If the system operates normally, there may be 3rd party applications which are causing a problem. Try deleting/disabling the third party applications after a restart. For each disable/delete, you will need to restart if you don't do them all at once.
I think some sort of process isolation prevents mail app to use the already build cache for All My Files and tries to recreate it causing a long time, especially if you have too many files.
I fixed this by right clicking on All My Files in Finder, adding a new search criteria for "created within last 7 days" and saving it as "All My New Files". I use this instead in mail.