Ah, got it. Must have missed that build. I was thinking of Queen of the Mississippi, operated by American Cruise Lines (along with the American Queen, now). I'm guessing both companies inherited the Majestic America mailing lists, since we get stuff from both.
Our trip on the lower Mississippi was special. Not so much because of the sight along the waterway -- mostly trees, and brown water -- but instead because of the attractions of the boat itself, and the level of service they provided. We've been talking about the Columbia/Snake trip for several years, but keep getting distracted...