This is probably a duplicate question, but I will still sum this up for you:
When you are creating APK, you use a keystore file containing a certificate to sign it.
Then, when you want to issue and update, certificates in old and new version must match, otherwise the system does not allow you to install it.
You most probably created this keystore file when you first generated the APK and then just forgot about it, so it is possible it is still sitting comfortably somewhere on your harddrive. You should look for it first :)
(They are quite small, 1-2kB, and every IDE has default path where to save them, so try creating a new one, see where it got saved and look if there isn't another similar file)
If you can't find it, it's time to panic. You are pretty much screwed if you want to issue and update. So, lesson number one:
Always backup your keystore files.
(I still do not understand why this is not shown as some big red flashy box during the APK upload dialog on Google Play :D)
So how to deal with this? You can change your package name, create new keystore, back it up, generate APK, unpublish your old app, publish new APK with same name and info.
Good luck with this. This almost made my hair gray this summer, so hope it won't happen to you :)