SSH Clone Permission denied (publickey) (AGAIN!)

I've seen this problem being issued several times already, but here's my particular situation. I've deleted all my SSH keys from my Gitlab account because I wanted to add a new one (specifically created to allow me to connect to my Gitlab account). So I added my new public SSH key to my Gitlab account, and when I tried to clone a Gitlab repository I get the eternal error:

Permission denied (publickey).
fatal: Could not read from remote repository.

Please make sure you have the correct access rights
and the repository exists.

if instead I also add my first created SSH key to my Gitlab account I can now clone a Gitlab repository using SSH. How can I solve this problem? And more importantly, why is this happening?