Why does Birthday attack work only with random messages and not with chosen messages?
Birthday attacks do indeed work also for messages chosen by the attacker. For example, consider the case that I want to get a collision between a letter of recommendation and a letter that I was fired. I can prepare $2^{n/2}$ letters of the first kind and $2^{n/2}$ letters of the second kind, and then we expect there to be a collision between a message of the first kind with a message of the second kind. Note also that it's not hard to prepare such letters. All you need is a number of ways of replace enough words. For example, consider "[Mr. | Dr. | Prof.] [Yehuda | Y.] Lindell was employed as a [security | cryptography] consultant in our [company | organization]." This sentence can be written 3 x 2 x 2 x 2 =24 different ways (and this is just one short sentence).

I would also like to note that it's even possible to carry out a low memory birthday attack on meaningful messages. But, I'll leave working that out to you as an exercise.