Finder doesn't come back after crash or `killall`
I have exactly the same problem on a MacBook Air, 13" late 2010 running 10.8.4 (12E55). I tried re-indexing as proposed without any change.

I could trace down my problem now to running "Virtual Box 4.2.16" with specific configurations of sharing the OSx drive/folders with the windows environment.
Don't run Virtual Box - and no problem will occur. This is my actual solution for solving the finder problem. 

Since VB 4.2.16 is the latest release there seems to be no help at the moment.