Interesting point!
However, I can think of a couple of ways of sidestepping it to have a Newcomb problem without lies:
Omega may be able to predict your reaction without simulating you at all, just like a human may be able to perfectly predict the behavior of a program without executing it
Omega could tell you "Either I am simulating you to gauge your response, or this is reality and I predicted your response" - and the problem would be essentially the same.
So it mostly seems to boil down to the implementation details of Omega.
Omega may be able to predict your reaction without simulating you at all, just like a human may be able to perfectly predict the behavior of a program without executing it
If you perfectly predict something (as Omega supposedly does), you must run a model on some hardware equivalent.
Unless you subscribe to special pleading similar to "if a program does not run on silicon based hardware, it's not truly run" - as Searle does with the special role attributed to the brain - you should expect that model that predicts your reaction to be essentially...
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.