Nintendo of Japan recently posted a 5-minute video explaining the many features of Brawl. In one section of the video, the sticker-collecting feature is shown off. A small set of icons along the bottom shows which character can equip each sticker, and originally showed small icons depicting Ness, Jigglypuff, and Lucario.
Nintendo of Japan has since updated the video, conspicuously whiting out these icons and effectively assuring us that this is "for real." More than simply confirming new characters, this news also confirms that the Brawl roster will exceed those characters announced on the official blog, which is just good news for everybody. Check out the original, unedited footage after the break. The icons appear very briefly around 4:20.
[Thanks to everyone who sent this in]