Funny enough N.o 25 was the only one they happened to mention in the FAQ, they apparently found it by the school. .....
In any case I loaded up a backup save I made before finishing New Island, which unfortunately had 12 tunes collected already and 25 was one of them. But I collected the other ones anyway and noted the location where I found the person.
4. Next to the Hot Spring to the N.E. of Castle Town. 5. Behind the tree next to Skinny Ray's classroom and the flying machine. (Farmlands.) 7. On the north side of Soup Church, in Castle Town. 8. Just south of the eastern Farmhouse in Farmland. 10. By the Knight statue in Solder Town. 12. Under the left lamppost, next to the Gourmet Town sign. 13. Along the wall east of the eastern Stonecutting Plant in Stone City. 14. On the east side of the Red roof, kebab house in Gourmet Town. 15. Behind the Cow Shed in Farmland. 16. In the inside corner of the L-shaped (clothing) house, which is next to Solder Town's cannon. 19. Behind the tree north of the King's Natural Reserve gate. (Behind a Glamour Town mansion.) 21. In the passage south of the mansion west of the hospital, south of the theater. (Glamour Town.) 22. By the tree behind the Hospital in Glamour Town. 23. Between the Eggan Civilisation Ruins' gate and the Stonecutting Plant in Miner's Town. 26. On the sand of Over there Beach. 28. Atop the Drain Cover on the N.w. side of Royal City. 29. On the N.W. side of the Theater in Glamour Town. 30. Final tune quest after collecting the other 29 tunes. (Alpoko Castle 5-7pm?)
Note that they won't appear every night, you might have to wait several days before they appear in a location.
I could guess some other locations, but might end up confusing them with wandering singers. I'm also not planning another play-through any time soon either. ---