It is very important to note that using brute force is NOT the answer! Initially, I tried to use just some pliers at the points where the green arrows are (photo in step 3), and NOTHING happened! After thinking about it overnight however, I employed the technique I have described here (using just my fingers) - the link almost fell apart in my hands! No pliers or force required.
The Powerlink is two pieces, each being a combination of a outer plate and a pin. The pins latch into the hole in the opposite half of the Powerlink. Alright, you know all that. The part that you may not be aware of is that the pins have a bit of a "head" on them that sit in an inset in the other plate. This makes it impossible to release the link when the plates are out all the way. They have to be pressed inward ever so slightly to get the head out of the inset. Take a look at the photos.