اصلا نیازی به تغییر versionCode و versionName  نیست (ما این مقادیر رو هنگام انتشار نسخه جدید، تغییر می دهیم و در مرحله تست برنامه اندروید، نیازی به تغییر اجباری آنها نداریم).
این مراحلی که ذکر می کنم را با دقت و دقیقا با ترتیبی که بیان کردم انجام بدهید تا دقیقا مشکل را بیابید :

اگر برنامه اندروید روی گوشی نصب است، ابتدا برنامه اندروید را از روی گوشی uninstall کنید. بعد فایل apk از برنامه اندروید ساخته و با انتقال آن به گوشی، آن را نصب کنید. بعد از نصب، از برنامه خارج شوید و دوباره همان فایل apk را اجرا کنید تا دوباره نصب شود. در این مرحله، نباید هیچ مشکلی به وجود بیاید (در این حالت، هیچ کاری با برنامه eclipse نداشتیم).
اگر بار اول برنامه نصب نشد، یعنی برنامه دیگری (غیر از برنامه شما)، با این نام package در گوشی وجود دارد (البته این مورد برای شما وجود ندارد چون موفق شده اید یک بار برنامه را روی گوشی نصب کنید و تنها برای کاربرانی نوشته ام که بعدا این موضوع را می خوانند). اگر بار دوم نصب نشد، باید بررسی کنیم و ببینیم که مشکل از چیه.
خوب حالا دوباره برنامه اندروید را unnstall کنید و به سراغ برنامه eclipse رفته و این بار از طریق گزینه Run AS در برنامه eclipse ، برنامه اندروید را نصب کنید. حال از برنامه اندروید خارج شده و این بار سعی کنید با فایل apk برنامه اندروید را نصب کنید (از طریق خود گوشی اندروید)، اگر نصب نشد، فایل keystore متفاوت بوده و یکی از مراحل یکسان کردن فایل keystore برای برنامه eclipse را اشتباه انجام داده اید.