People are saying it's '2.5D'. It's hard to tell exactly from the trailer since the quality is so bad, but it still looks like good ol' 2D art to me. Though it does appear to be at a higher resolution.

A new Samurai Showdown was shown at the AOU expo as well, but the Kotaku dude didn't seem to like it (though he described Zangief in his SF4 impressions as 'that wrestler guy', so his opinion is barely credible to me :P).