n
is the exponent. So when n
is doubled from 64 to 128 it doesn't mean that you have to try twice as many values. It means that you have to try $2^{64}$ times the amount you were already trying (as $2^{128} = 2^{2\times64} = 2 ^{64+64} = 2^{64}\times2^{64}$).
It is required to only search half of the key space on average (if average is the correct term here, this is not something you are likely to repeat), but that means that the search should cover $2^{128}/2 = 2^{128-1} = 2^{127}$ on average.
So in the end it comes down to the difference between $2^{128/2}$ as used by the birthday attack (which is not applicable) and $2^{128} / 2$ which is the average amount of tries required by a brute force attack.
For an indication how the time scales with the number of bits, take a look at the stats of the RC5 72 bit challenge and compare it with the stats of the RC5 64 bit challenge that you probably referred to.
Birthday attacks are indeed not applicable to encryption. Collision finding - for which the Birthday attacks are used - are in itself not directly applicable to attacks on ciphers.