I had a bit of a poke around the interwebs, and I think I found the solution.
To fix, Dave Coyle ran in terminal:
$ sudo rm -r /.Spotlight-V109
to delete the existing index. (This of course didn't do anything for me as I had just trashed the folder)
$ sudo launchctl load -w /System/Library/LaunchDaemons/com.apple.metadata.mds.plist
$ sudo mdutil -i on -E /
The terminal then showed:
Spotlight is now busy re-indexing my drive. Yay! (assuming it all works once the index is complete).
Thanks for the effort Clockwork, it helped put me on track