How funny to fall upon this from one day ago and I am getting the exact same error while trying to stake from the cli.
I followed exactly this to register my keys:
https://docs.cardano.org/projects/cardano-node/en/latest/stake-pool-operations/register_key.html
and then this to stake:
It seemed to work for one address, but for another address I keep getting the same error as the original poster. Maybe because I have 2 UTXO for the same address? I have chosen the older UTXO to register and to stake.