I think picking pretty well known characters as much as possible would help with the guessing. Main charcters from series that have gotten a lot of TV coverage for instance (One Piece, Naruto, DBZ, FMA, Inuyasha, Kenshin, etc...) and series that have been around and popular for a long time.. (Tenchi, Oh My Goddess, Cowboy Bebop, Gundam Wing, Sailor Moon, etc...) Plus characters could be recycled throughout the con too.
I would be willing to type up a description (a paragraph or two) for each character to hand out to those who couldn't guess their character, to sort of introduce them to it. Perhaps that would turn them on to some new anime as well.
All in all, I think it could be made as easy and fun as possible.