Treecko, Jirachi is a Steel/Psychic; it's already been done.
As for Diamond and Pearl, there is no doubt in my mind that the games will introduce an entirely new set of monsters to catch, and thus providing us with two legendaries (or starters) that coincide with a diamond or pearl theme. Gonbe's appearance in Dash hints at this: they've always been sneaking Pokémon from the next generations in with the oldies near the brink of a new series. Example: Marill appeared to the general public in the first movie. This was back when Mewtwo was the toughest, which was long before Chikorita~Celebi were ever officially listed.
As to what these cover monsters might look like, well, at this point it's anyone's guess. Not that it was obvious with the previous games when they were new, but at least back then they were simplistic colors, and not...jewlery.
