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
In the video, by the looks of it, the tube is overall hanging down. Even when wriggling the general orientation is still down.
I don't think the vena contracta aspect makes any difference here.
How I would approach this:
I imagine the water flow initially very slow, and the rate of flow is gradually increased, to explore the entire range of rates of flow.
The lower the flow rate the lower the exit velocity of the water.
When water exits a nozzle (more generally, when any fluid/gas exits a nozzle) there is a recoil force. If the nozzle would be secured to some cart then the recoil force would propel the cart.
At low flow rate the force of gravity is larger than the recoil force at the nozzle. The larger the flow rate, the larger the recoil force. At some flow rate the recoil force will be enough to lift the nozzle against gravity.
The tube is flexible, so the tube bends. That makes the nozzle point sideways. With the nozzle pointing sideways the tube is moved sideways, and gravity has opportunity once again to pull the nozzle down.
The result is that the nozzle is violently swinging from side to side, flexing the tube all the time.
In addition there is the inertia of the water flow in the tube itself. When the water is forced to move along a bend in the tube the inertia of the water will tend to straighten the bend, contributing to the overall chaos of the motion.
Best Answer
This is correct, in a sense. The effect of an adverse pressure gradient is to decelerate the flow near the body surface. This can be seen, for example, by examining the boundary layer equation in two dimensions.
$$\frac{\partial u}{\partial t}+u\frac{\partial u}{\partial x}+v \frac{\partial u}{\partial y}=\nu\frac{\partial^2 u}{\partial y^2}-\frac{1}{\rho}\frac{\partial p}{\partial x}$$
If you consider steady flow and assume normal velocities to be small, then by inspection, we can see that an adverse pressure gradient causes $u$ to decrease in the streamwise ($x$) direction.
As you suspected, separation requires that the flow near the boundary stagnates. Moreover, separation occurs when the flow actually reverses. $$ \frac{\partial u}{\partial y}_{y=0}=0; \quad \text{Flow Stagnation / Impending Reversal} $$ Additionally, it requires that the pressure gradient be simultaneously adverse, so that the the flow does not accelerate again. $$ \frac{\partial p}{\partial x}>0 \quad \text{Adverse Pressure Gradient}$$
So, in short, you're correct. However...
The two statements are essentially the same - there are any number of ways to physically describe what's going on- but I think you've got the causality mixed between the two. The curvature of a body, and thus its attending streamlines, jacks up the adversity of the pressure gradient along that body (assuming you're past the point of minimum pressure). So it's the adverse pressure gradient that ultimately leads to separation. In a perfect world, where viscosity didn't exist, the flow would speed up as it hits the forward part of a curved body. The pressure would drop as it reaches the widest point of the body, streamlines are "squeezed" together, and the flow reaches a maximum velocity. On the afterbody, the flow would decelerate and the pressure would increase until both reach their upstream values. It's a simple trade between kinetic energy (velocity) and potential energy (pressure). In a real viscous flow, some of that kinetic energy is dissipated in the heat-generating nuisance that is a boundary layer, so that when the transfer from kinetic back to potential energy occurs on the afterbody of a curved surface, there isn't enough kinetic energy, the flow stagnates and reverses, and you get flow separation.
I can't comment on shock-induced separation, as I work in hydrodynamics and don't worry about compressibility. I'm no authority in that area, either, so if somebody takes issue with my explanation, feel free to criticize.