Remember that the complexity to brute force AES-128 is 2^64 due to the birthday paradox. The complexity to break AES-256 is 2^119 and thus it is still harder to break than AES-128.
I'm not sure how you could use the birthday paradox to brute force a block cipher. You have a message you want to decrypt, and you don't know the key. A brute force attack is trying all the possible keys (2^128 for AES-128) and on average you will find the right one with 2^127 guesses.
