I started with Rand al Thor, which it got easily. I tried to shake it up by trying F.E.A.R.'s Point Man, a complete non-character, and it still got it. I then tried Nien Nunb, Lando's copilot from Return of the Jedi. It even got that; this thing has a ridiculously extensive database.
Edit: Well, I finally found one that it didn't get on the first try: Huan, Luthien's dog from the Silmarillion. The first time it guessed Oy, from The Dark Tower. It still got him on the second try, but it's something of a victory. This is after it got Feanor on the first try.
Edit Edit: Ooh, I'm only the 31st person to try Huan. I thought he was a pretty well known character, at least among people who had read the Silmarillian. Then again, how many people are there that got far enough into that book to get to the Lay of Leithian?
Final Edit: I finally managed to stump it, with Emperor Elagabalus, an obscure, much hated Roman Emperor.