Personal experience - I have a 15 kilo road bike and a 19 kilo high racer recumbent bike.
On the flat I can do approximately the same speeds on both bikes as shown by this 5.17 km flat stretch with 5 traffic lights.
On a local climb of 404 metres at 7% average, I took 49 min 31 on the bent and all my times on the road bike are between 30 min and 33 1/4 minutes.
Finally - I've only got 220 km on this recumbent so far, and there are a number of things I want to change when money permits, which should help with the overall speed at least on the flat.
EDIT After about 6 months, my bent's odometer is now 4,418 km and I'm commuting 25 km a day each way. The bent is great for travelling consistently. The average speed once at-speed is easily 4-7 km/h faster than the road bike, and for significantly less effort. My HRM shows 20 BPM lower on the bent. A headwind increases the difference in speed and effort. A gradient, well that's where the road bike blows the bent away.
For safety the bent is awesome - some of my commute is narrow and every single driver has seen it and adjusted their on-road position to go around me. When on the same road on an upright, there's at least one close pass every couple of days. I think this is to do with looking vastly different.
Slow speed control and riding in close traffic is another failing for lower bikes - you're literally harder to see when below a 4WD's window-sill. So I have DRLs and a chopper flag, and I'm not slow to shout if required.