Though I referenced "motivation" earlier for simplicity, the underlying psychological mechanics I want to build in are much more complex than motivation. I've been researching an interesting cross-disciplinary domain between psychology and technology and have learned that it IS possible to use computer or mobile devices to motivate and shape the habits of a person. For the actual implementation of that, I'm still tweaking it around, but will hopefully be able to have some experiments out by this summer or fall. Of course, I could always try the faster route and find someone else to build the app for me, but I like programming enough that I want to achieve the self-satisfaction of building the first prototype at least.
(A semi-success story. After the past 2 years of tweaking and examining our assumptions, my sister and I have successfully designed a self-sustaining system that keeps her engaged in what she wants to learn...on a 10-hour daily schedule, she's learning 3 languages, music and other subjects without supervision (she's 15). It's more rigorous than her high school curriculum but it's amazing how lighting-speed she learns when she's in this state of flow everyday. Now hopefully what I've learned from this can be applied to many other people too.)
The one aspect of your discussion that I tend to disagree with is that these apps you were searching for weren't providing what most people are looking for - motivation. I think based on the fact they are searching for the apps in the first place shows they already have motivation or they would not be searching for such help. I'm not exactly sure how an app would motivate a person to exercise besides being an alarm clock letting them know to get up an hour early to exercise. I probably am missing a potential solution here but I am interested in seeing your app.