I tried "Cory Booker," mayor of Newark (recently on The Colbert Report). It asked me the same questions several times but worded differently, and in the end it guessed Obama (though not surprising since Booker isn't as famous).

http://www.20q.net always amazed me.