What most people usually mean by "complex" software is that its Kolmogorov complexity [0] is high (even if they don't know what Kolmogorov complexity is). You can think of this like saying "it takes a lot of software to correctly describe the shape of the problem and its resulting solution".
This is different from "it's hard to figure out how to represent this problem and its solution in software". For a crude analogy, E = mc^2 is a very simple equation, but it was very hard for humans to figure out. In other words, it was extremely difficult — but it wasn't necessarily complex.