Before I start the answer, I'd like to point out that Bernoulli's principle is not applicable directly when you're comparing air flow from two different sources ( or two different flow fields, according to Wikipedia ). It only relates the speed and pressure of air within a single flow field.
Now let's consider the first case where you blow over the sheet of paper. The paper would not rise if it were flat, even though you are blowing air across the top of it at a furious rate. Bernoulli's principle does not apply directly in this case. This is because the air on the two sides of the paper did not start out from the same source. The air on the bottom is air from the room, but the air on the top came from your mouth where you actually increased its speed without decreasing its pressure by forcing it out of your mouth. As a result the air on both sides of the flat paper actually has the same pressure, even though the air on the top is moving faster. The reason that a curved piece of paper does rise is that the air from your mouth speeds up even more as it follows the curve of the paper, which in turn lowers the pressure according to Bernoulli's principle.
If Bernoulli's principle were to hold true in the first case, it would then imply that the paper would droop downward in the second case, when air is blown below the paper. But this is clearly not the case. The upward pressure gradient in this downward-curving flow adds to the atmospheric pressure at the lower surface of the paper. This resulting pressure gradient is the source of lift in the second case. I hope this answers your question.
Reference: Wikipedia
EDIT - A formal derivation of the mathematical relation between curved streamlines and pressure gradients can be found here: https://ocw.mit.edu/courses/aeronautics-and-astronautics/16-01-unified-engineering-i-ii-iii-iv-fall-2005-spring-2006/fluid-mechanics/f20_fall.pdf
EDIT 2 - Lift is also generated by the Coanda effect. Here a couple of links:
How is lift generated due to Coanda effect?
http://en.wikipedia.org/wiki/Coand%C4%83_effect