I don't think Jeff is right about Disguise. I played Brotherhood and that had the same challenge, and I completed it by just playing as each of the original characters(not any preorder or DLC characters). Doing that in Revelations though, doesn't work(as you say). The new DLC characters also aren't enough to get the challenge as I got them the other day, played them all and still haven't unlocked the first level of Serial Killer. All I can assume is that there's either some bug or glitch that needs taken care of, or that for some stupid reason, the Ottoman Doctor(the only character not in my list) is included in the characters needed to be played. My money is on a glitch or bug though, because although I don't have the doctor, I have played as him in team matches where the team leader had him in thier list, and that should have been enough. I've also heard that the new trophies that come with the character DLC aren't popping either(though I haven't confirmed that myself). If that's true, then I assume they'll release an update at some stage that hopefully fixes both issues. Serial Killer is a very easy challenge to get, so I'm not fussed as long as they take care of it eventually.
Also, I tried playing as evey character I have in my list after downloading the DLC(thinking it might have stared the count again) and that still had no effect.
The only other thing I think it could possibly be is that you have to play as every character in a single sitting, without signing out. I might try that next...
Edit:
Well I tried playing as every character in a single sitting last night and it didn't work. My new theory is that it might require having unlocked and purchased (with Abstergo credits) every character upgrade for weapons, visuals, taunts, stuns etc... and then to have played a session with every character. This would obviously take a lot of sessions, but luckily, I've played a lot, so I'm not too far away from trying it out.
All I need is about 300 credits worth of stuff for the Vanguard and everything for the Sentinal, which is probably about 1000-1200 credits worth, give or take. This will still take a while for me to check, maybe a few days, or a week, but I'll come back and post the result when I know. Unless of course the issue gets solved in the meantime. Knowing this game as I do, my money is still on a bug or glitch as the cause.
2nd Edit:
I got the first level of Serial Killer today. Though I'm still unsure of the exact cause of the original problem. The was an update yesterday which probably fixed it(and gave us "new" maps on sony network), but I did buy the last character upgrade today before the challenge popped, so I can't be sure. If someone gets the challenge without buying all upgrades for all characters, then perhaps they can answer to comfirm what's required.
I don't think the DLC characters count, for what it's worth, since I haven't been using them much.