Well, there is no proof to the Sheik thing, she may be dropped for a more independent Twilight Princess Zelda, maybe not. We won't know until TP release.
I can't think about many Mario deserving characters. Toad is always there, he rocks and could fit. Geno is third party, but he reps HIMSELF but HIMSELF, it's one of these unique and special standalone characters like Alucard from Castlevania SotN. Of course, no Waluigi, no Petey, no generic enemies. Paper Mario could work, but he hasn't many "paper" based moves: Plane, boat, roll... then a hammer, jumping... he may look neat, but he hasn't many original paper moves, of course Sakurai could make them...
I don't like Bowser Jr, but he could work, not as a Bowser clone but as a new and original character. I just feel that his presence won't add too much to Brawl.
Mario is in a tight spot. Actually the four main characters (Mario, Luigi, Peach, Bowser) are being repped. Yoshi went solo. Wario went solo. So that leaves few interesting choices: Toad, Geno (will he go solo?) and Bowser Jr.