This is interesting news, but even if your software uses AES, there's nothing actionable in it for you.
You are 10,000x more likely to get busted up by a flaw in how you use a cipher than you are by a flaw in what your cipher is. You could use TEA, and it would still be overwhelmingly likely that your code would fail before the algorithm did.
In fact, anything you did to react to news like this would probably make you less secure. That's because AES has overwhelming library support, and whatever "stronger" cipher you might think of adopting won't. That means you'll have more DIY code, and more poorly reviewed library code, all with a bunch of implementation flaws lurking under the surface.
They describe that the attack depends on "minimizing the number of active S-boxes in the key-schedule" and that AES-192 is harder to attack than AES-256 because the key schedule has "better diffusion".
I'm guessing that they don't mention AES-128 because the attack simply doesn't work against the 128 bit key schedule for reasons related to the increased difficulty of attacking AES-192 with this technique.
I'm pretty sure the cryptanalysis is equally applicable. The summary (and maybe the paper) don't mention AES-128, but the attack uses "boomerang attacks, which are based on the recent idea of finding local collisions in block ciphers". This might affect AES-256 more than AES-128 because there are more chances for local collisions, but it will still be stronger.
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.