I wasn't perplexed, but I have to imagine that most people younger than us were. As you said, the Weird Al song came out while Art Fleming was still best known for Jeopardy!, but the show was gone, and it was shortly after that that Alex brought it back. Also, the video lampoons the old Art Fleming set, not the nifty new LED-powered Alex Trebek set. And to be fair, I've never actually heard anybody wonder who Art Fleming is or why he's mentioned in the Weird Al song, but I'm sure that today, if you ask anyone who the host of Jeopardy! was, they'd tell you it was Alex, not Art.