For those who haven't played XD, Battle CDs were training programs that gave you a preset Pokemon/Team, and placed you into a battle situation that (ostensibly) had one real solution that you had to figure out. They were essentially Pokemon battle-based puzzles to be solved.
They should do something like that again in this game. They were fun as tutorials to advanced techniques, but, more importantly, the advanced ones were fun and often very difficult to figure out the solution to. I'd like to see them return.
"It was like unwrapping a wonderful present -- a present made out of presents." - Graham Linehan, describing the Legend of Zelda: Majora's Mask