Found the problem. The Reminders App doesn't like location based tasks and Exchange.
I have my works Exchange account setup on my phone and Reminders was set to sync with it. I went into my mail settings and turned off the reminders sync. Went back into the reminders app and voila, location based tasks are enabled in my iPhone 4
[edit]- I tried it on my iPad, and still no dice. I assume that's because I have the wifi version. I'd imagine those with 3G iPads, should be able to get location aware tasks to work once they stop reminders from syncing with an exchange account.