Kyuukon, dammit! It'd be sweeter if history repeated itself with Haruka... watch the Katsura gym battle to see what I mean. ^^
All the Houen fossil Pokemon besides Armaldo. The afforementioned Nokotchi, Lanturn, Hariisen, and Samehader. Speaking of the last three, it'd be nice if we saw water Pokemon battling on land more often. Despite what they lead on, they're perfectly capable of moving and fighting on land. Kasumi's Tosakinto, in the first mini-movie, hopped on its belly, and was only a touch slower than the other Pokemon. Bigger Pokemon, like Laplace and Whaleou, I imagine could use their fins to slide around like a sea turtle on a beach (hey, these Pokemon aren't exactly speed demons in the games). Oh yeah, they really need to show a Doble using Sketch, as well as a Butterfree using a god damned psychic technique.