Have you ever seen one of the systems that provides the background for an instrumental player, and can figure out where you are when you start and stop? They're really cool. I also knew a guy who worked on a system that would identify music--- you called their service on your cell-phone and let it hear what was playing in the background. So I think the technology is there.
A lot of different variations can be created. Oldies, J-Pop, Jazz Standards, you name it. But the best tie-in would obviously be to make an American Idol themed version. Release a new CD of popular music from the show each year, have Simon chew you out, etc.