Yeah, the AppleCare CDs are always a version behind, they can never boot the very latest Mac models.
Note that it makes no difference what OS you have installed on the hard drive.
In any case, wait a few weeks, then call Apple, and get them to send a new CD. You may have to try a few times: in the past, people have had trouble with Apple sending them the same (unusable) version repeatedly, until finally getting a warehouse manager on the phone to actually fish out a copy of the correct version.
Macintouch.com has an extensive discussion on this.