And there's no warning, either to the consumer or the retailer,
Yes, there is. It's in the EULA, clear as day. Just read it.
You do read the license agreements for the programs you purchase... right? (if not... tusk, tusk to you...)
I know game companies have it in for the used market these days, but customers aren't to blame for it and shouldn't be punished.
I agree, with the latter part. The customer is not to blame. (To the former, that the game companies have it 'in for' anyone, well... they have to protect their own interests as well. Without some kind of protection, one copy of the software could mean millions of unpaid users. And Stardock's way is much better than anyone else's.)
Unfortunately, the retailer that sells used software doesn't always comply with the EULA of the software manufacturer. And when that is the case, someone ends up with the short end of the stick - usually the customer.
The only hope for the OP is that they can return the product and obtain a refund - or go to the expense of bringing legal action against the retailer in the hope of a profitable settlement.
Or, GraemeCaUK could request of Stardock a new serial number (at some little expense to said person) to make his/her/other copy legitimate.