hyperref and algorithm2e line references

I like to use the hyperref and algorithm2e (Release 3.9) packages when creating documents with LaTeX. Unfortunately, there seems to be a slight incompatibility:

Suppose I process the following with pdflatex:

\documentclass{article}
\usepackage[naturalnames]{hyperref}
\usepackage[linesnumbered,boxed]{algorithm2e}
\begin{document}
\begin{algorithm}
First\label{line_1}\;
Second\label{line_2}\;
Third\label{line_3}\;
\end{algorithm}
First is on Line~\ref{line_1}, second is on Line~\ref{line_2} and third is on Line~\ref{line_3}.
\end{document}

Then I get:


The line references don't work -- even though they were meant to be fixed in Release 3.3 of algorithm2e according to the change log! A quick fix is to use the [naturalnames] option of hyperref package and comment out lines 845, 847, 849 and 850 of algorithm2e.sty to get (lines 844 to 853 shown below):

\newcommand{\nl}{%
%  \@ifundefined{href}{% if not hyperref then do a simple refstepcounter
    \refstepcounter{AlgoLine}%
%  }{% else if hyperref, do the anchor so 2 lines in two differents algorithms cannot have the same href
%    \stepcounter{AlgoLine}\Hy@raisedlink{\hyper@anchorstart{AlgoLine\thealgocfline.\theAlgoLine}\hyper@anchorend}%
%    \stepcounter{AlgoLine}\Hy@raisedlink{\hyper@anchorstart{AlgoLine\thealgocfline.\theAlgoLine}\hyper@anchorend}%
%  }% now we can do the line numbering
  \strut\vadjust{\kern-\dp\strutbox\vtop to \dp\strutbox{%
      \baselineskip\dp\strutbox\vss\llap{\scriptsize{\nlSty{\theAlgoLine}\hskip\skiptotal}}\null}}%
}%