You do not want to format your External Hard Drive (EHD), doing so will cause you to lose everything on that drive! You are lucky that Disk Utility prompt came up, because that is not something you want to do.
While it is a good idea to keep your music on an EHD, I would recommend storing your music in two different places: one in your computer, and another in the EHD. This does two different things; helps the iTunes program identify music files quicker, and gives you two copies of your files (just in-case something bad happens to either drive).
EHD's are great for storage purposes, but programs do not seem to run as optimally towards files found on an EHD. iTunes must first read the files on the EHD before the program can give you any real control, the process usually takes a few seconds longer compared to files that are already stored directly on your computer.
I wish i could be more help, but the file index
you are talking about seems to suggest that something might have happened to your files.. but I'm not exactly sure.
Edited by Curious Mew, 04 April 2012 - 10:42 PM.