Can't install Android app after signing

I am getting ready to publish and Android app and it was going great untill I got to the point where I signed the app (creating keystore and stuff). Right after I did that I could no longer get my app to work, getting these errors during Build and Run:

Installation failed with the following output: pkg: /data/local/tmp/Package.apk

Failure [INSTALL_PARSE_FAILED_NO_CERTIFICATES]

829 KB/s (10466485 bytes in 12.329s)

UnityEngine.Debug:LogError(Object) PostProcessAndroidPlayer:UploadAndStartPlayer(String, String, String, String, String, Boolean, Boolean, Boolean) (at C:/BuildAgent/work/14194e8ce88cdf47/Editor/Mono/BuildPipeline/PostProcessAndroidPlayer.cs:882) PostProcessAndroidPlayer:PostProcess(BuildTarget, String, String, String, String, String, String, BuildOptions) (at C:/BuildAgent/work/14194e8ce88cdf47/Editor/Mono/BuildPipeline/PostProcessAndroidPlayer.cs:464) UnityEditor.HostView:OnGUI()

and

Error building Player: UnityException: Unable to install APK! Installation failed. See the Console for details.

I tried to go back to unsigned developement build, but then when I Build and Run I only get black screen upon running the app. The mobclix adds are also visible, and menu music is playing so the game seems to be running, but the screen is black. So yeah, pretty much stuck now...