iTunes 'FILE COULD NOT BE FOUND' message

Hi-
I have all my music on an external hd. I have my preferences set to look for my music on the hd, in the file where it is.
On most all albums that I play about 1/2 the songs 'could not be found' and I'm prompted to locate them or to cancel.
I find them right where they should be when I choose to locate them.
Additionally, when I close itunes and reopen it it makes me locate them again.

This is new. I used to have the same setup, but recently got an additional hd to be really safe. I reorganized some files, consolidated some stuff, but didn't change much really.

Any ideas?
Thank you

Thanks for the reply.
Not sure how to make sure it's mounted correctly. If it weren't mounted correctly would this problem make sense? It seems like none of the files would be able to be located? But I don't know much about it.
I do always connect the hd before I open itunes.
Thanks for your help

I'm using a MacBook 10.6.8. A WD Passport, I think it's 500gb.

What am I looking for to make sure it's mounted correctly?

Thanks