In the past I've done C25K, but have always had trouble once the intervals stopped. I met a girl in November who uses intervals (Inspired by Jeff Galloway, I think) and she even did them in the NYC marathon. With her we started doing 30 sec walking/30 sec running, which was a bit too much for me, but I was able to keep up with her doing 1 min walking/30 sec running.
But that was when I'd been walking regularly which I haven't been now for a few months. So I thought I'd start with 2 min walking/30 sec running and decrease the walking until I get to the 30/30 and then try to increase the running. I think I'd like to get to 5 min running/30 sec walking and possibly even just do that for the 5K. We'll see how it goes!