It's easier for me to control for the things you know rather than guess at what one instance has shown.
- How many iPhone 4, iOS 5.0.1 does the app show in Location Services?
- What can not prevent an app from registering for Location Services?
- What can make a delete / reinstall not actually clean the user data from the device?
Could there be a systematic issue? If yes, ask for time to reproduce the issue. If not, then you have to look at either the device or the OS install.
It's frustrating to hear that your device isn't running properly - but it's hard to guess what step is best next for both you and the user until you have agreement on how to attack the problem.
In this case - the third question is likely the issue (assuming you have good data on the app working in general). I would engage the user - say you've had reports of an uninstall not working unless some extra steps were performed.
I'd ask them to connect to iTunes or make an iCloud backup - since when an app fails to install, something is certainly wrong - you don't want to be around when worse happens, telling a user to do X and Y if they don't have a backup.
Then really deleting the app data is crucial.
- delete the app from the device
- power off the device
- reinstall the app over the air to ensure it's a clean install with no settings
- test before resorting to a restore of the device (or restore and set up as new)
I would also encourage your user to come here to learn and ask - this community has lots of experience to help solve user-level issues and having more developers and new users around can only help.