Strange. It worked for me a few months ago. Maybe you need to do "sudo apt-get update" first?

Bitcoin Core works for bitcoind. You can also use Bitcoin ABC or Bitcoin Unlimited if you want to mine Bitcoin Cash.