One possible explanation:
If you reinstall windows 10 (in case this is about 10), and you use a very old version (lower than v1511), it will not recognize partitions encrypted by Bitlocker of a higher version and throw "recovery key incorrect" even when it's correct.
To overcome this (in case it applies): update windows to a current build.
--
If however the recovery key ID does not match the ID that windows requests, then this is a totally different story. So that should be checked as well.