Hi Whippet,
No mystery at all.
You are allowed to have two computers activated at the same time. Activation (or 'sign in) means that the license agreement is linked to the particular computer, its hardware and OS. If your old computer failed and got completely reinstalled, the first activation was lost (broken identification for the activation servers). Then, the second activation was used; such circumstances are exactly why you have got two activations (it's also to allow one to use alternatively two computers).
Now, you are on a new computer. There is no activation left. The message tells you to deactivate on your previous computer (menu Help >> sign out). Then you can enter and validate your license key.
It's rather common to have a computer stolen, broken or lost. That's what happened to you the first time. To recover that activation, you must use the 'Customer Care' help option, choosing by chat and specifying it's an activation/license problem. Adobe staff can quickly remove the lost activation if your previous computer is no longer available.