Я прошел через это при переходе с Win на Linux.Я смог просто скопировать исходный файл хранилища ключей на ваш новый компьютер и использовать его для продолжения подписи.Eclipse / ADT предложит вам использовать хранилище ключей, когда вы выберете Export Signed.
Если вы подпишетесь с новым хранилищем ключей и попытаетесь загрузить apk как обновление для существующего приложения на Маркете, это не разрешит.