The answer is "it depends". It depends on the specific problem you are trying to solve. If you are training a classifier to determine whether or not an image contains a face, you can get away with reducing the size of the image quite a bit. 32x32 is a common size used by face detectors. On the other hand, if you are trying to determine whose face it is, you will most likely need a higher-resolution image.
Think about it this way: reducing the size of the image removes high-frequency information. The more of it you remove, the less specific your representation becomes. I would expect that decreasing image size would decrease false negatives and increase false positives, but again, that depends on what kind of categories are you trying to classify. For any particular problem there is probably a "sweet spot", an image size that yields the maximum accuracy.