Something similar happened to me once with my Creative Zen music player, and since you're storing music on your drive it could be the same issue. If the directory structure of your music results in really long path/file names -- if you have something like...
E:\MP3\Genre\Rock\Artist\Artist - Album\Artist - Album - Song.mp3
...those long paths can cause temporary errors. This is especially true if the drive is a cross-platform Mac/Windows drive (and if it's Firewire it probably is). If that's the case, when you do the disk check it will mention something about invalid long file names, and will fix them for you.
The other thing I can suggest, from my experience with an external DVD writer, is that plugging it *in* after you start the computer shouldn't matter, but *unplugging* it while the computer is on can cause temporary errors. If while the drive is plugged in you right click it, choose "Properties," go to the Hardware tab, choose it again (don't ask me why), click "Properties" again, and then examine the Policies tab, it will tell you if the drive supports hot-unplugging.
Finally, as always with Windows it's a good idea to check the disk vendor's website to see if they have updated drivers. Good luck!
MattD