The King DID lie, because he wrote the inscriptions. What is written on the inscriptions is inaccurate if the dagger is not in the second box.
Yes, this is really an issue of whether your choice causes Omega's action or not. The only way for Omega to be a perfect predictor is for your choice to actually cause Omega's action. (For example, Omega 'sees the future' and acts based on your choice). If your choice causes Omega's action, then choosing B is the rational decision, as it causes the box to have the million.
If your choice does not cause Omega's action, then choosing both boxes is the winning approach. in this case, Omega is merely giving big awards to some people and small awards to others.
If your choice has some %age chance of causing Omega's action, then the problem becomes one of risk management. What is your chance of getting the big award if you choose B compared with the utility of the two chocies.
I agree with what Tom posted. The only paradox here is that the problem both states that your choice causes Omega's action (because it supposedly predicts perfectly), and also says that your action does not cause Omega's action (because the decision is already made). Thus, wether or not you think box B, or both boxes is the correct choice, depends on which of these two contradictory statements you end up believing.