I didn't figure out how to make a connection between notes until I read your answer either.
One issue with (particularly) your second interaction option (dragging from the border of a note to another note) is that you also have a "resize horizontally" behaviour attached to the right edge of a note. That means I perceive the dynamic border that you show as existing for that purpose. Even once I've figured out that I can drag lines from that space, it also reduces the width of the target area that doesn't resize the note. Lastly, since the resize behaviour uses a different cursor, when the cursor doesn't change between the border and content I assume that there's no hidden behaviour.
In terms of fixing this, I'd implement anchors whose sole purpose is to allow me to drag a connection between elements. These anchors could be hidden until a note is focused or a connection is dragged near it. OmniGraffle calls these "magnets" and presents them like so (notice that the selected node—Publish article—shows all four of its magnets, but as the cursor is dragged toward the Editing article node its closest magnet is shown dynamically):
Image from Getting Started with OmniGraffle 5