iTunes has a neat way to figure out which playlists (if any) your music belongs to so that you can put things right where you want them to go. All you need to do is right- or Control-click on the song, album, or artist in question and pick “Show in Playlist.” From there, you’ll see the associated playlists for that item, and you can click on any one of them to jump right to it.
(If what you've chosen isn't in any playlists, that "Show in Playlist" option won't appear.)
That was quick! Well, just because you guys are awesome, here’s another playlist tip for you. If you want to see which songs aren't in any playlists, start by creating a smart playlist (File> New> Smart Playlist or Option-Command-N):
Then in the window that appears, change the first drop-down to “Playlist,” the second to “is not,” and the third to the name of one of your existing playlists.
Click the plus button on the right to add more rules, and create a new one for each playlist you’ve got.
This is obviously kind of a pain if you’ve got a million billion playlists, but you gotta do what you gotta do.
Finally, if you keep a ton of TV shows, movies, and so on in iTunes, you might also want to add the rule below to make the Smart Playlist only contain music:
When you’re finished adding in everything, make sure that "Live updating" is checked (so any new music you add will follow the rules you've just set), and click OK. Your new Smart Playlist will appear, ready for you to name it and then go through and assign those songs to playlists.
678 songs? Geez Louise. I think I’ve got some work to do over the weekend. I'm such a party animal.