@arisel: thanks, that confirms our current theory. It is most likely so that installing Aptoide and/or Here befre installing Android APp Support brings in ‘apkd’ to the phone unnecessarily. This is turn prevents installing Android App Support.
Deleting apkd at the command line (like you did) or uninstalling Here and Aptoide should help.
Edit/few minutes later:
Yes, uninstalling those apps helps, tried myself.