How can I write a paper that will convince the reviewers that the results are non-trivial? I submitted a paper in math/cs/economics to a top-level journal. The paper involves a new variant of a well-known problem. All reviewers agreed that the results are interesting and non-trivial, but they rejected the paper as not being general enough for their journal.

Encouraged by the positive feedback, I submitted an improved version of the paper to a medium-level conference. The improvements include simplifications of some of the proofs and additions of stronger results about the same problem. Now the reviewers rejected the paper claiming that the results are too weak and unsurprising!

What should I do in the next time I submit (to a different journal), in order to make the reviewers believe that the results are indeed surprising and non-trivial? I don't want to write the proofs in their more complicated version, as in the first revision, because this is unscientific. But writing it in a simple way seems that doing so creates a false impression that the results are too simple. What do you suggest?
In the end, the significance of a scientific advance is determined not by how complicated it is or how much hard work was put in, but by comparison with what was known / possible before.  

It sounds to me like you need to have a much clearer and stronger comparison with the prior state of the art, particularly emphasizing why the new result makes a difference to larger or deeper issues.  Depending on the nature of your work, this might mean anything from a little improvement on the prior work section to introducing new sections with explicit comparisons.

For example, if you were able to mathematically compute the Nash equilibrium for preference of donuts vs. muffins, that's a nifty little result, but it might seem obvious or insignificant.  If you can explain that this was something impossible with prior methods, because nobody had previously been able to deal with the breakfast uncertainty principle, then that is surprising and interesting.  If you can show that your result accurately predicts sales in major chain stores, then that is also surprising and interesting.  In either case, you are showing how your result has implications outside of just being a result.

Now, you could probably also make your work appear harder and more significant by obfuscating the mathematics, and that might "work" for purposes of getting this paper accepted.  I personally, however, consider that to be scientifically dishonest, and would strongly recommend against that.  Remember, that your colleagues are not stupid, and sooner or later, people will realize that you are fluffing up your results, to your detriment.