When you tick the box to back up, you're prompted for a password. Your Mac sends a request to your phone, "Now encrypt all backups with this password." Every time your Mac asks for a backup from this point on, your phone streams a backup to it that is encrypted with the key you gave before. Observe that nothing about this process requires the same Mac to be used for the "set password" and the "backup" requests. Crucially, your Mac need not remember that password, your phone does.
You've hit a very unfortunate but all-too-common scenario, namely, that you forgot your backup password when it came time to restore. I suppose Apple could have reduced the odds of this happening, by demanding that you verify your backup password when it notices it's partnered with a new Mac and you request to restore. But it doesn't, because backup and sync are different things that can be performed separately. I'm very sorry you find yourself in this situation. Try to recall your encryption password--that's the one you set when you first ticked that box to encrypt. You need that. Otherwise, I'm afraid you'll be starting from scratch.