Are you completely sure that you added the tracks to the playlist? It's possible that if your playlist was named by artist or album, that you accidentally dragged the files into the "soup" portion of the tree.

You sound pretty definite, but I'd like to eliminate this as a possibility before we start looking at more esoteric causes.