First, you misread the page: this is not about collisions. The Wikipedia page says:
the cost of finding a set of CGA Parameters that yield the desired 59 bits is approximately O(259)
The important word here is "desired". The attacker wants to find an input that hashes to a specific, given output. This is called a preimage attack. By contrast, a collision attack is about finding two distinct inputs that hash to the same value, without any constraint on that common output value; this is not at all the same thing (and collisions are in fact vastly easier, down to about 230 evaluations for a 59-bit output).
That being said, the average attack cost is indeed 259, not 258, because this is a hash function, not a block cipher. You speak of "searching half the namespace" but there is, in fact, no such thing as a "namespace" in that case.
When you try to brute-force a 59-bit key, there is a defined space of possible keys (all 59-bit sequences) of size 259, and you know that one of them is the solution, and you can try them all in due order, without ever trying twice the same. Under these conditions, you can expect to find the right one after, on average, trying half of the possible keys.
This is not so here. In the case of CGA, the problem is about finding an input (which is quite larger than 59 bits) such that the output is a specific target 59-bit sequence. As you try various possible inputs, you get the corresponding outputs, but (that's the critical point) these outputs are (from your point of view) random (as in "random oracle"), and, in particular, you may get the same one several times. In fact, it is expected that you will get your first duplicate after trying about 230 inputs or so (that's the so-called birthday paradox), and, as you accumulate such random outputs, you will get more and more collisions. If you try 259 distinct inputs, and hash them all, then you will not get all 259 possible outputs, but substantially fewer (about 63% of them).
In other words, when you do the brute force attack on the hash function, some of your effort is wasted, because it yields 59-bit outputs that you already had with another possible input. This lowers the success rate, and thus increases the overall attack cost.
Assuming the hash function behaves like a random oracle (i.e. no known structural weakness), then the probability of finding the right 59-bit output every time you try some new input is exactly 2-59, and, by definition, this means that you have to try on average 259 times before finding a match. This is an average: you may get lucky and find a match earlier; you may also get unlucky and find a match later, with no upper limit. This (again) contrasts with the "search the key for a block cipher" situation, where you know that the attack will work after trying, at most, all possible keys; in the preimage attack for a hash function, you do not even get such a guarantee, only an average.