How about some sort of hide and seek game that utilizes online leaderboards?
Here's the idea: The app has admins that place 'beacons' at certain locations around your town/city/state/country. The user is given clues as to where the beacon is, and is given x attempts per day to find the beacon.
The beacon is not a tangible object, of course. Instead, it's just a GPS location that's stored in a database somewhere. I imagine the user would go to a location that they think contains the 'beacon', press some big friendly button on their iPhone, and see if they've found the right spot. If not, they have x-1 more tries to find it that day. If so, they get a point and get online bragging rights.
There wouldn't be any real reward to the game other than having a nice big number next to your name on the leaderboard. I imagine it would inspire competitions among iphone users who have a lot of free time on their hands.
Maybe players with a lot of points could place their own beacons once a month or something. Also, maybe you could work out something with an advertiser to have some sort of contest where the winner gets some sort of tangible prize (gift card, etc) or have all the users end up in their store (Starbucks, etc).
Just an idea.