“Overexposed” doesn’t begin to cover it. After innumerable recent releases, not to mention all the seventy-fifth birthday hoopla, Willie Nelson again? You’d think no one else made records in Texas. Actually, Two Men With the Blues (Blue Note) was recorded in New York City. What distinguishes it from the others? Willie’s partner, for one—esteemed New Orleans trumpeter Wynton Marsalis, the artistic director of Jazz at Lincoln Center—and the band, Marsalis’ straight-up jazz quintet, for another. If the thought of Nelson’s singing in such company conjures unpleasant duet memories of, say, Julio Iglesias, think again. This live recording swings, and Nelson fits in like another hepcat. There have always been jazz inflections in his vocal style, both in tone and timing, and here he uses them to full effect. Despite a couple of clunkers, “Rainy Day Blues” and “Night Life” are terrific, and hearing Nelson launch into one of his famed meandering guitar solos in the midst of such harmonic mastery only adds to the fun. Plus, anything that loosens up the notoriously uptight Marsalis can’t be a bad thing.