K-Means initialization
The nth centroid is chosen from a distribution proportional to $D(x)^2$, but pay careful attention to how $D(x)$ is defined.  From the paper (top of page 3):


  In particular, let $D(x)$ denote the shortest distance from a data point to the closest center we have already chosen.


Notice that $D(x)$ is the distance from $x$ to the nearest centroid.  Compare that to the description of how you are choosing the points:


  I repeat this and calculate distances from the red point to all remaining points and take the furthest away, but this puts me back near the green point, but I was trying to get to the center cluster.


Instead of computing the distance between all remaining points and the red point, you should instead compute the distance between each point and its nearest centroid.

For the points in the cluster around (1, 1) you'll compute the distance from the red point, and all the distances will be relatively small.  Similarly, for the points around (-1, -1), you'll compute the distance from the green point, and all these distances will be pretty small.  

However, for points around (0, 0), some of them will be closer to the red centroid and some will be closer to the green centroid, but they are not very close to either one.  This means that $D(x)$ will be large for points in the (0, 0) cluster, and you are likely to choose one of these points as the next centroid.

Does that make sense?