Yep - I managed to get the old O-ring stuck in the hole too, without realizing it at first. What I thought was a very worn-down O-ring on the old sensor turned out to be just the tarnished brass on the sensor itself, so I spent a while trying to jam the new sensor + O-ring down on top of the old one, dribbling coolant all the while, before I figured it out.
That connector was what really had me fooled, though, even though (I thought) I knew how to disengage it. It just takes a lot of force to open the little tab, along with (as paramedick said) some reverse pressure first.
I would definitely recommend removing the old sensor, still plugged in, before trying to unplug the harness connector. It would have been even harder otherwise, or I would have broken the plastic clip that holds it in.
You live, you learn. Bruises heal and fingernails grow back eventually.