Certainly not always; I would even go so far as to say that there is a point of diminishing return. At some point a game can become so complex that it becomes too much.
Looking at complexity with respect to ‘realism’, it is fairly well known in the design of simulators for training that novices have trouble attending to the task if the simulated environment is too complex. Too many distractions interfere with learning, so they start off with a fairly simple environment which becomes more complex as they become more experienced. If we look at it in terms of fun, people tend not to have fun when things are too hard.
In entertainment games, especially RPGs, complexity of environment can definitely make a game more fun – Skyrim is an excellent example. Visual complexity can also add to the fun – it is one of the things I like about both Machinarium and Tiny Bang Story, but I don’t think visual complexity can compensate for poor functionality or gameplay.
However, the opposite can also be true. Games can be fun precisely because of their simplicity. One of the games I like to play is Flow Free and part of the appeal is the simplicity of the mechanic and play as well as its visual simplicity.
If we are talking about educational games, I think we have to be very careful about adding anything that does not directly support our instructional goals. That’s not to say we should avoid it, but we should always ask how this adds to our objectives. Sometimes, making it more fun by adding extra options can be a good thing, but I think it all depends on how it is designed. Adding complexity per se does not, in and of itself, make anything more fun.