It depends in part on what the players find complex/complicated.
It doesn't seem like the problem for the OP was in character creation, but during play. A fighter [or thief], during play are simpler. You don't have daily attack powers to worry about, and you only have a single (multi use) encounter power to use, and for the most part it's not extremely complex of deciding when to use it since they are free actions which don't require you "risk" that they don't work.
A mage, on the other hand, requires you to do some character building every "morning" in determining your spells for that day. During the fight, you have lots of options and need to decide which to use (and what it does, etc). Now, with the warpriest and mage they have at least reduced the odds of "wasting" an encounter power by giving effect or miss effects to most of the powers in the book so missing isn't a waste of a limited resource. Still though, having your options limited makes decisions in play easier.
The 3.5 warlock seems like a possible example of what a 4e spellcaster would look like if built like the thief/slayer/knight.
You have the at-will "basic attack" with your eldritch blast.
You have stances (well, invocations) that modify it, either changing the size of the attack (two targets, cone, part of a melee, etc) or the energy of the attack (fire, cold, acid, with associated secondary effects), all of which were at-will. Then you had the other invocations that would mimick spell effects, often buffs (i.e. utility powers).
I'm not sure if that is what the hexblade will be (the name does seem to suggest otherwise) but it could be a caster that is built in the "mold" of the essential martial classes.
Also, one "simplicity" that was available to 3.5 casters isn't available to 4e characters (except for the essential martials, and psionics) is the ability to "spam". A sorceror, for example, could use up all his level X spell slots casting the same spell over and over. 4e doesn't work the same way because of it's set up (you only have one 1st level daily "spell slot" regardless of level) but he inability to pick the same spell again in your 5th and 9th level spell slots, etc means that choosing to use certain powers also means not being able to use it again for the rest of the encounter and/or day which is not just a tactical option, but a long term strategic one (well, at least with dailies). If you knew that, even if you used this, you'd still have 2 more "copies" for later, it's easier to just concentrate on "is this a good time to use this" instead of "is this the best time to use this, or will there be a better time later".