Is your fan pushing the air the wrong way? It should draw air in and blow it toward the engine. Don't laugh, I've heard of it happening before.
Another thing it could be is that the lower hose is collapsing from water pump suction at higher rpm and pinching off flow. Make sure you run a nice new hose with a spring inside it to keep it from collapse.
