Saw this thread pop up on one of my occasional wanders through...
I just read Sharon McCrumb's "Songcatcher" (no relation to the movie, I believe). The search for a long-lost ballad (which McCrumb actually wrote for the book) is central to the story.
Another story I have looking around (and this one's difficult to find) is Poul Anderson's novella "World Without Stars". There's a song called "Mary O'Meara" whose lyrics crop up verse by verse as the story unfolds. For those of you in FSGW-land, it's one of the songs I sang when I hosted the "Songs From Literary Sources" Open Sing last year.
I could probably find more SF with musical bits if I went and trolled my bookshelves...