Sorry, I'm a bit late to the discussion...

So here's an idea. Make the problem easier. Instead of trying to get full geographical localization through GPS or cell phone towers, perhaps it is possible to get the same usefulness out of relative-location based on WiFi access points.

That is, you map certain WiFi MAC addresses to locations i.e. "when you see access points A, B, and C, that means I'm at home. when you see D, E, and F, I'm at work"

It won't be as sophisticated as say... reminding you to get groceries if you're near a supermarket. But this kind of information might still be enough for you to put basic reminders in like "Don't let me leave the house without my passport tomorrow", or "When I get to the office, make sure to call Steve". And further, it doesn't require you to run GPS all the time. It just does the periodic wifi sweep it usually does...

Even that could work, if there are networks (with unique ID) around. You don't even need access to them, just acknowledge that they are there. Just name the location then you could reference it in reminders.

Of course then you need to have a PIM running all the time...