Have you tried following this tutorial : A new, community-hosted Unreal Engine Wiki - Announcements - Unreal Engine Forums
I haven’t deployed to Android myself. But just right clicking projects and setting dependencies there is not usually a good approach because every time you generate new project files all that information is lost. I would highly recommend following the tutorial above. I used it to link some libraries for my project and it works like a charm. I suspect your android woes can be dealt with a similar approach.