Unable to push/pull any gitlab.com repos

I’m sure I’m doing something silly here, but as an experienced user of github who has also successfully contributed to gitlab repos he didn’t create himself, I’m stumped.

I created a gitlab repo and added the specified git ssh URL as a remote and tried pushing and pulling. A whole lot of nope:

ERROR: Repository not found.
fatal: Could not read from remote repository.

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

So I triple checked that I added the right public key, matching the correct private key according to my .ssh/config. I did, and the same configuration works fine for github.

Oh well, so I tried https instead. Nope. Not even a password prompt.

I’ve seen it suggested that we work around the https problem by putting the credentials in the URL but this is obviously terrible security.

What am I missing? Is this a common problem?

Thanks!

To be clear, I’m talking about the hosted gitlab.com service for private repos.