El código que te puse debes poner dentro de la función para cambiar la imagen. Y sí, poniendo ese código no es necesario poner nada más para el enlace ya que el enlace ya está en el <a> que quedaría más o menos así:
Código PHP:
<a id='enlace' href='http://www.pagina.com/' onClick='cambioimagen();return false'>imagen</a>
¿Entiendes? El enlace ya está en el <a> solo que al hacer click en él la primera vez no entra al enlace ya que cancelamos la acción con return false, pero después hacemos que sí pase al enlace colocando return true.