Elvis becomes the other Elvis for the third episode of his weekly show, Spectacle: Elvis Costello With... (Wednesdays at 9pm EST/PST on the Sundance Channel), performing covers of "Mystery Train" and "Baby, Let's Play House". Pete Thomas and Davey Faragher are the rock-solid rhythm section, while nimble-fingered James Burton (formerly of Presley's TCB band in the 1970s) handles lead guitar duties. The band shines, especially Burton, whose licks ripple up and down the guitar's neck; Costello, on the other hand, takes too many liberties with the lyric's phrasing, eventually throwing Faragher's harmony vocal for a loop.

Despite its somewhat wobbly course, "Mystery Train" is an apt way to welcome native Arkansan and former President Bill Clinton, who speaks with Costello at length about music, politics, and the ways in which the two subjects often intersect.

"Who's the real king?" Costello asks Clinton immediately after the former President takes the stage. "You, him [Presley], or me?" Clinton counters with an anecdote about Ronnie Hawkins, who once told him, "There's no difference between me and Elvis but looks and talent." As a guest, Clinton is just about everything a host of this sort of show could want: formidable music expert (he flexes his geeky chops when talking about New Orleans, and calls Nina Simone's "I Wish I Knew How It Would Feel to Be Free" the "most under-appreciated song of the Civil Rights era" -- what taste, Mr. President!), humble student ("You can be really good, but you probably won't be great," he recalls telling himself when he decided to quit pursuing a career as a saxophonist), and a seeker who looks to have his preconceptions challenged (a particularly funny and enlightening moment occurs when he explains how his daughter, Chelsea, turned him into an appreciator of hip-hop).

The episode takes an unexpected left turn with its final musical performance: Pat Metheny and Charlie Haden show up to play a new acoustic composition, "Is This America? (Katrina 2005)". The song is tender and dreamlike, and perhaps even a bit inquisitive. Costello and Clinton look on as Metheny and Haden lose themselves in the language of plucked strings.