We had the same issue. I believe the “This key doesn’t match any account.” is a bug in the Chrome extension (I have at least one report that the Firefox extension wasn’t affected by this). As far as I understand it. the extension is supposed to query the server whether the key belongs to a known user in the database, but as far as I could tell, it didn’t actually query the server. There was no request in the Chrome inspector, and no request in the server’s access.log.
The workaround is to reinstall the extension; the recovery worked afterwards. Make sure you have your passbolt_private.asc key backup ready before you remove the extension, because uninstalling the extension without having a backup will make you lose your private key.