Just to reiterate what I was talking about. My laptop came with Windows 8.0 (Core). If I install windows 8.1 with media created with the media creation tool, it uses my 8.0 OEM embedded key automatically and activates online as soon as I have internet access with no issues. If Install 8.1 Pro with media created with the media creation tool, I get prompted to enter a product code. I can and have entered one of my TechNet 8.0 Pro (Retail) keys and it is accepted. Activates online automatically too.
If you refreshed the factory image with your recovery disk it should use the OEM key and activation should not be an issue. You mentioned that you were dual booting with Linux. Did you turn off Secure Boot or change any other BIOS settings? If yes, change them back to the original settings and see if your PC will then activate. To be honest I don't know enough about UEFI to say if that is your activation issue or not but it can't hurt to test it out. I've only ever run Windows and haven't messed with my laptops BIOS all that much.