Comparing a brute force attack on DES (with $2^{56}$ operations) to a birthday attack on CMAC (with $2^{64}$ operations) would appear to be an apples-to-Volkswagen comparison; they are assuming two things are similar, when they really aren't.
The brute force attack on DES involves obtaining a single plaintext/ciphertext block pair, and then going through the possible DES keys, and looking for a key that encrypts that plaintext block into that ciphertext block. The key here is that, once the attacker does have that plaintext/ciphertext pair, he no longer needs anything else from the attackee Alice -- he runs all these trial encryptions on his own hardware, and if he feels the search isn't going fast enough, he just buys more hardware. The speed of the attack is limited only by the attackers budget.
On the other hand, the birthday attack on CMAC involves asking Alice for the MAC of a huge number of messages (and then digging through those MACs to find a duplicate). The key point is that we need a great deal more from Alice; it is not sufficient to obtain a limited number of bits, instead if we need to generate the MAC of $2^{64}$ messages, that means that we need to present those $2^{64}$ messages to Alice, and we need her to compute the MACs of all those messages.
That's the key point: Alice will compute those MACs only so fast, and the attacker cannot speed it up by parallelism or anything. If Alice is able to generate only 1 MAC per nanosecond, that means that it'll take over 500 years to generate the MAC for all $2^{64}$ messages.
In summary: any attack that requires $2^{64}$ exchanges with Alice cannot be considered "somewhat trivial"; even if a brute force attack with the same abstract effort would be.
