There are no settings in the Reminders app that I can find. I have the Reminders selected in the iCloud settings. I can find no other places where Reminders should be selected. Still can't use location based Reminders.
Not sure what the problem is, but you can see that I don't have an iCloud reference in Reminders, and I do have Reminders selected in the iCloud account info. I also have an Exchange account, but there is nothing that I can find that interferes with Reminders.
Having had your problem, here's the best answer I have for all experiencing this problem.
When you installed iOS5, you decided not to turn on the iCloud for Reminders. W/O iCloud enabled for Reminders, you created a folder for Reminders. This folder is linked to your phone, not the iCloud. Every Reminder you create is under this folder. And, even though you have now ENABLED the iCloud for Reminders, you are still creating Reminders in the folder that is linked to your phone.
FIX: With the iCloud enabled for Reminders, create a new folder for Reminders. You should now see your new folder listed under "iCloud" and your other under "Exchange". Create a new Reminder under your iCloud folder name and the Location option will be available.