a birthday attack reduces the number of keys you have to search by half, not half the number of bits. This means that you would have to search 2^255 keys instead of 2^256 keys.
Look again. Finding a collision in a hash function with n possible values takes an expected number of guesses proportional to sqrt(n). If n = 2^256, then sqrt(n) = (2^256)^(1/2) = 2^(256/2) = 2^128.
