I bought an external HD to store all music on. Once I moved all music files from my internal HD to the external I started having these issues. It is teh suck.
i have a 500gig hard drive devoted to music files and i have no such issues. are you on a mac or pc? it might be worth your while to reinstall iTunes and start over, dunno.