Android APKをGooglePlayへデプロイするには、署名されたAPKを準備してデベロッパーコンソールへアップロードしますが、「アップロードしたAPKが、まだ有効になっていない証明書で署名されています。署名について詳しくはこちらをご覧ください。」と表示されることがあります。
ADTやeclipseプラグインをアップデートしても問題が解決できませんでしたが、
以前アップロードした別のアプリケーションのKeystoreを使用して署名したAPKだと
アップロードできました。
原因は不明ですが、既にアップロードしたアプリのKeystoreを使うことで暫定的な対処ができそうです。