If you find yourself in a situation where no cache is being found in your restore cache step, and the saving cache step states the cache already exists, double check the checksum. The cache key is generated using the checksum of the file provided in your configuration, often a "lock" file.
If this file is modified in any way between the restore and save steps, you will have mismatching keys, meaning you are attempting to save your cache to one key, and restore from another, which will always fail.
Why does this happen?
Check to see if there is any reason your lock file is being overwritten at any point during the build process, this may happen during an installation step.
If you are using Ruby Bundler and have a version mismatch between your local dev environment and the CircleCI environment, the bundle install step will overwrite your Gemfile.lock and cause the issue mentioned above.
Always verify parity between your local and remote development environments.