I got 85% for the Coca Cola logo on the first try and only from memory. On this same first try at the end of the session my average score is 80% (I got the wrong blue (I thought it was darker than it actually is) for IBM and got 47% for it, lowering quite a bit the average). Also I'm not a designer or anything close to that, I'm a computer science student.

This to say I don't think it is an "impossible task".

EDIT: just got a friend (also not a designer, and with an (in my opinion) extremely bad taste in colors :-p) doing the test and he got 78% average, with 100% for Apple (he's not an Apple user) and Shell, 99% for Batman, 97% for Coca Cola, but 0% for Dropbox ^^.

So this confirms that it is far from impossible.