"Computational complexity" is a measure of the CPU / RAM effort involved in the execution of an algorithm. In the case of an attack over a cryptographic algorithm (e.g. MD5), complexity is measured relatively to the attacked algorithm. MD5 processes data by 512-bit chunks, so it has an "elementary cost" which is the amount of CPU it takes to hash a small message (of 0 to 447 bits, to be precise). Since MD5 offers a 128-bit output, so, for a preimage attack (finding m such that MD5(m) = x, where x is given), the generic "get lucky" attack has average cost 2128 times the cost of hashing a small message. Indeed, the "get lucky" attack is about choosing random m until a match is found, which, for a "perfect" hash function (a random oracle) works with probability 2-128 for each try.
Therefore, we express "CPU effort" as the number of times the attacked function could be evaluated with that many invested clock cycles. This measuring unit has the nice property of easily showing whether a function is "academically broken" or not. The "get lucky" attack is generic: it works for every hash function, regardless of its perfection. The average cost of that attack is 2n for a hash function with a n-bit output. So any attack which does better, even slightly, counts as a "break". In the case of MD5, the presented attack has cost 2123.4, which means that it is about 20 times faster than the "get lucky" attack. But it still completely infeasible in practice. Realistic limit for a powerful attacker (say, someone with the budget of Google) is around 280 invocations of MD5.