How to solve installation errors reported by users, on Android?

One thing you could do is ask your user to download a logCat app from android (for example aLogCat, which is open source), then try to install your app, then send you the resulting log.

Based on this log you could investigate why your app is not installed.

You probably do want to ask them what device, Android version, rooted or not, etc, they are trying to install on and at the very least log it to look for trends. If there's some particular device (or set of devices with particular features), you may eventually spot the pattern.

This shouldn't preclude other efforts, but it's definitely a first step toward figuring things out.

To expand on @XGouchet's answer:

(I realize that this may not be the best approach, but it is a means to an end)
Perhaps it would be better to include aLogCat in a testing version of your apk with an install tie-in to send logs on a timer to a server or something (until this problem has been adequately documented, and make sure you put this fact somewhere in the download description). One approach might be to re-structure your app so that the apkd is actually a wrapper that installs aLogCat and then starts the install for your app. This way the end user has to take no extra steps, and you get much more info on the issue(s) and can fix the problem. _Again, make sure you put a notice somewhere in the download description that you are doing this and only do it as long as it takes to make sure you have the issue identified*._ You will likely be skewered if you do not disclose this fact and loose all creditably in the Play Store if you don't let people know what and why you are doing. Once you have a handle on the possible source, revert back to the unwrappered apk.

Only give the "logging" version to users that have reported the issue and are willing to help with some testing. Would be (mostly) simple for everyone involved, just have the wrappered version on your site somewhere (Again, with the proper disclosure) and direct your testing users to this apk with directions for enabling the "Unknown Sources" option.

At that point, you're on to a whole new question: how to fix it (probably better to ask that question on SO).

*If you let your user's know that you are doing this and why, you are likely to get less emails asking questions, less negative feedback/ratings, and less general bad karma. But some might be turned off by the extra recording so be ready for that; this is why I said to do this only as long as needed! Remember to let your users know that with the logging you might get some sensitive info, let them make an informed decision.