I don't think he's actually lying at all. In the simulated world, the simulated coin came up tails. He's not lying about the coin flip result, he's simply talking about a different coin.
Why does it make sense to accept the simulation as a "real person" that can be "lied" to, but not accept the simulated world they exist in as the "real world" in which they exist? Maybe we're all being simulated and their world isn't any less real than ours. The "simluation" might not even be running at a deeper level (i.e. within this simulation) - Omega being from "outside the matrix" is certainly one way of explaining how Omega manages to be so darn clever in the first place...
The simulated you will presumably not gain $1K/$1M worth of utility from taking the simulated $1K/$1M (if it does, then it's a different problem).
Just developing my second idea at the end of my last post. It seems to me that in the Newcomb problem and in the counterfactual mugging, the completely trustworthy Omega lies to a greater or lesser extent.
This is immediately obvious in scenarios where Omega simulates you in order to predict your reaction. In the Newcomb problem, the simulated you is told "I have already made my decision...", which is not true at that point, and in the counterfactual mugging, whenever the coin comes up heads, the simulated you is told "the coin came up tails". And the arguments only go through because these lies are accepted by the simulated you as being true.
If Omega doesn't simulate you, but uses other methods to gauge your reactions, he isn't lying to you per se. But he is estimating your reaction in the hypothetical situation where you were fed untrue information that you believed to be true. And that you believed to be true, specifically because the source is Omega, and Omega is trustworthy.
Doesn't really change much to the arguments here, but it's a thought worth bearing in mind.