Fixed this by removing this file in each workspace:
[workspace]/.metadata/.plugins/org.eclipse.e4.workbench/workbench.xmi
Opening STS from the command line (on mac: ./STS.app/Contents/MacOS/STS -clean
) and viewing stack traces on startup led me to this answer: https://stackoverflow.com/a/13884461/1637003
Now all the random ways this bug was manifesting itself have gone away: JUnit tests not running, cmd+clicking to open declarations not working, various MatchLocator errors on startup and shut down.