To be honest, at the beginning of Spirit Tracks, I was under the impression that Chancellor Cole was going to turn out to be Ganondorf. I'm not exactly sure why I felt that way; perhaps it was all the hanging around the royal family and attempting to take their power through deception.
I agree, though. Malladus really felt like your bland, cut-and-paste, garden-variety villain, with no real distinguishing features or a noteworthy past. Chancellor Cole was much more interesting.