Why are collision attacks important when talking about MAC schemes? I'm reading Ferguson, Schneier, and Kouno's Cryptography Engineering, and it has a section on MACs. It discusses different types of MACs, but it seems to claim that to acheive 128-bit level security, you need a 256-bit MAC due to the birthday attack.

Why is this the case? Why are collision attacks a concern in MACs? I think that to break a MAC, you need a preimage attack to guess the plaintext, or a second-preimage attack to forge messages. In these cases, the birthday attack is irrelevant since it only finds some random collision, which may not be relevant to the data stream being attacked.

What am I missing? It seems that in general 128-bit MACs are much more popular (GCM and CCM and all those fancy AEAD modes have 128-bit authentication tags); surely they can't have only 64 bits of security? Is Cryptography Engineering simply paranoid?
The attack outlined by Drlecter is valid for any deterministic MACs (that is: with the MAC a function of message and key) with an iterated structure and an $n$-bit state. It relies on internal state collisions, expected to occur after about $2^{n/2}$ messages (the birthday bound), that can allow forgery once discovered. I'll illustrate this in the case of CBC-MAC with a 64-bit block cipher (e.g. 3DES) operating on fixed-size 3-block messages (24-byte) with 8-byte MAC (the full block cipher width).

The adversary asks for the MAC of $2^{33}$ messages with random first two blocks and the last block fixed. It is expected that a collision occurs, and the adversary then has $(M_0||M_1||M_2)$ and $(M'_0||M'_1||M_2)$ having the same MAC, with $M_0\ne M'_0$. So far, this is not a break. But notice that, with certainty, the collision has occurred after the second block, and continued after the third.

Now, for any last block $M'_2$, $(M_0||M_1||M'_2)$ and $(M'_0||M'_1||M'_2)$ collide with certainty. That allows the adversary to predict the MAC of one of these messages by querying for the MAC of the other, which is a break.

Thus a deterministic MAC with $n$ bit internal state (and output, but in itself truncating the output does not help much), after $q$ queries with the same key, has become unsafe with odds about $q^2/2^{n+1}$, for $1\ll q\ll2^{n/2}$. E.g. after $2^{60}$ queries, HMAC-SHA1 has odds $2^{-41}$ to be vulnerable.

Note: This attack (or any generic attack with similar result that I am aware of) does NOT in general apply to iterated MACs with an $n$-bit output. E.g. HMAC-MD5 or CBC-MAC-AES truncated to $64$-bit are not awfully vulnerable to this attack; after $2^{40}$ queries odds that the attack works are $2^{-49}$.