From Birnam Designs Wiki

I had a notification message saying that Tracker encountered a problem, and that there was an index corruption. The only option was to reindex the entire computer. To do this right, do a hard reset first.

First make sure you have the right utils (you might already):

sudo apt-get install tracker-utils

Then run a hard reset

tracker-processes -r

You can restart the tracker without having to logout/in with:

tracker-applet&
/usr/lib/tracker/trackerd&

Thanks sarutv!