Is there a way to gradually increase the speed of a video? For example, the video will start at normal sped and then gradually get faster until it's 50% faster.

A "normal" speed increase can be achieved by applying the speed effect located in the motion folder in the effect list.

A gradual increase is not yet possible (the speed effect is not keyframeable).

After nearly a year and trying many programs I've finally come across a way to do keyframed speed changes. You can read about it here http://askubuntu.com/questions/17885/can-you-do-keyframed-speed-changes-with-video/

Keyframed speed changes can also be done in Cinelerra (ReframeRT effect), if that happens to work better for you than Blender. Thanks for the tip about Blender, though. Blender isn't very full featured as an NLE, but it actually has a few interesting features that would be nice to have in kdenlive, I'd love to see something along the lines of meta-strips in kdenlive. I just posted a feature suggestion for that in the brainstorming forum.

A crude way to do it in Kdenlive is to split the clip up into a several pieces and adjust the speed in steps.

Only problem is when you have a lot of speed changes and want to modify any of them. Just takes a loooooong time!

Here's what I achieved with Blender. I modified the sound in audacity http://www.youtube.com/watch?v=zV4Ur3J6blE