From the error message I would say you have mixed up the keystores, or android studio is just using the wrong one to do the release build. The best way to be completely sure is to clearly setup your build.gradle, and build it yourself on the command line using
./gradlew clean assembleRelease
What is probably happening is that Android Studio is using your debug keystore (ie. the default) to sign the release build because it can't find the original keystore you used in eclipse, or you have the wrong password somewhere...
Have a look at this configuration, note the location of the keystores, the naming convention and how it corresponds to the build.gradle. Note the signingconfigs and how they are setup for the release build. To build from the command line, simply cd into the directory with your "gradlew" file, and run
./gradlew clean assembleRelease
to build the release apk, or
./gradlew clean assembleDebug
to build the debug apk. If it fails, try
./gradlew clean assembleRelease --stacktrace
Screenshot of build.gradle and filesystem setup
But please remember not to put your keys in your source control! That means editing your .gitignore file.
There is a stack of information on how to do this here:
http://developer.android.com/tools/publishing/app-signing.html