I've had problems too but this is what I have discovered. Firstly, reminders only uses the GPS occasionally. It relies more on cell site and wifi data to figure out where you are. Battery saving i suppose. Secondly, the location it uses when you set a reminder is very vague. My home address comes up as "54-146 some street" As I have my exact address stored in my phone as "74 some street" the location reminders fail when I select home as the reminder location. If I use google maps to store that vague address in my contacts as my home address I can select that as my location for the reminder and it works perfectly!
Hope I explained that ok.
Sent from my iPhone iOS5 using Tapatalk