How to put the QED symbol of a proof at the right place inside align?

Change the order, this works just fine, amsthm after amsmath, otherwise it might be a bit hard for it to hook into align*

\documentclass[a4paper]{article}
\usepackage{amsmath}
\usepackage{amsthm}
\interdisplaylinepenalty=2500
\usepackage{amssymb}
\usepackage{hyperref}

\title{Example to Show QED is Misplaced}
\author{}
\begin{document}
\begin{proof}
This proof is typeset correctly:
\begin{equation*}
x = y + z \qedhere
\end{equation*}
\end{proof}

\begin{proof}
But this one not!
\begin{align*}
x & = u + v \\
& = y + z \qedhere
\end{align*}
\end{proof}

\end{document}

Section 5 of the amsthm package documentation contains the following.

When used with the amsmath package, version 2 or later, \qedhere will position the QED symbol flush right; with earlier versions, the symbol will be spaced a quad away from the end of the text or display. If \qedhere produces an error message in an equation, try using \mbox{\qedhere} instead.

However, when I tried this with your example I got a QED symbol one quad away from the end of the display, despite the fact that my distribution contains amsmath version 2.13. However, using

\tag*{\qedhere} 

instead solved the problem.