As valve is tweaking the relative new Steam-API branch we use,
please try to link accounts again with the following additional variables:
1) Steamclient not running
2) Steamclient running in online mode
3) Steamclient running in "offline" mode
We like to give clearer instructions or solution,
But as we did not change anything on our side
(beside a small change around Christmas 2014 that fixed the sudden link failures in mode 3).
Unfortunately it changed behaviour again without any step from our side.
Also make sure you do not use the Steam built-in browser, start the link process with your usual browser from here:
Please reply the version that did not work and which one then worked for you,
to forward this to valve and our registry development to see where they or possibly we need to take care of.