This doesn't sound like a market problem so much as a business model issue. If one of the free apps does what people need, they won't pay for a $5.00 version, even if it's slightly prettier. Hell, a quick look at the Apple app store lists apps that range from free to $3.00. I'd suggest changing your business model.
Try in-app ads with a lower cost ad-free version (say $1). Or add features that are both extremely useful and hard to duplicate for a competitor that is working for free. Some ideas: GPS proximity alarm when passing a grocery store, or a tie in to a desktop client or website.