I forwarded this upstream and according to a tracker developer, the nautilus tracker plugin will be going away soon, to be replaced a feature directly in nautilus.
For a more immediate solution there are a few things you can try: * Waiting for tracker-store to complete it's integrity check. This could be several hours for a large database, possibly longer. * Or, soft reset the tracker database with "tracker-control -e". The tracker database will be deleted and restored from backup. * Or, hard reset the tracker database with "tracker-control -r". The tracker database will be deleted and recreated.