Hah, that's fun. My o3-mini-high transcript didn't hint that it recognized the puzzle and looked legit when I scanned through them, but I'm still very suspicious since this is evidently such a classic puzzle.
I should have changed the cigarette brands to something else too.
If you want to make a cosmetic change to the puzzle, you might try eliminating the massive quantity of implicit information in "the green house is immediately to the right of the ivory house".
After doing some substitutions on what it means to be in positions 1/2/3/4/5:
A. If the ivory house is in London, the green house is in Madrid.
B. If the ivory house is in Madrid, the green house is in Kiev.
C. If the ivory house is in Kiev, the green house is in Oslo.
D. If the ivory house is in Oslo, the green house is in Tokyo.
E. The ivory house is not in Tokyo.
9. Milk is drunk in Kiev.
11(A). If the man who smokes Chesterfields lives in Tokyo, the man with the fox lives in Oslo.
12(A). If the man with the horse lives in Oslo, Kools are smoked in either Tokyo or Kiev.
15(A). If the blue house is in Madrid, the Norwegian lives either in London or in Kiev.
[...]
Another easy change is to exchange categories. Swap the animals for the drinks and instead of "the Spaniard owns the dog" and "the Ukrainian drinks tea", you'll have "the Spaniard drinks tea" and "the Ukrainian owns the fox" (depending on which equivalences you decide on). It won't make any difference to the puzzle, but it will permute the answer.
Try flipping the order, adding a few nonsense steps and combining 2 steps into one and also splitting a single step into two. And then see what happens and post it here. :-)
I should have changed the cigarette brands to something else too.