I like this idea a lot. It takes a lot of motivation for me to get up and exercise, and a good reward program would help a lot.

My one suggestion, to help adoption, is to integrate the app with some of the existing fitness devices that have open APIs. For example, I wear my Fitbit all the time as a watch, so it would be great to be able to import those stats into Walky even if I'm not walking with my phone all the time.