I solved my problem.
We have the upstream repo at CoinsManager/CoinsManager, which I forked at Fandekasp/CoinsManager. And when running travis encrypt, travis is getting the repo name from my origin remote, instead of querying the heroku git repo.
Therefore, I needed to specify the correct repo as follow:
$ travis encrypt -r CoinsManager/CoinsManager $(heroku auth:token) --add deploy.api_key