Al final lo que he hecho es que el usuario introduzca su nickname y su email, y si se encuentran registrados en la base de datos, y coincide dicho nickname con el email de registro, se le envia un mensaje al correo indicado con la nueva contraseña, e indicandole que si accede a su perfil en el sistema, podra modificarla por la que prefiera.
 
Me funciona correctamente asi que aqui dejo parte del codigo por si le puede ser de ayuda a alguna otra persona:  
INTRODUZCO EL NICK Y EL EMAIL
 -miro en la base de datos si esta registrado dicho nick
    -ESTA REGISTRADO
       -compruebo si coincide el email introducido con el de registro de dicho nick
            -SI COINCIDE
                 --> Envio el nuevo password al correo (enviarnuevopass.php)
            -NO COINCIDE
                 --> Muestro un mensaje que indica que el registro de dicho nick no se hizo con el correo introducido 
    -NO ESTA REGISTRADO
       --> Muestro un mensaje que indica que no se encuentra registrado dicho nick 
codigo enviarnuevopass.php 
Código:
    function enviarnuevopass($nickname,$email)
	{
	   conectar(1);     //Funcion que me conecta con la base de datos
	   $pass = substr(sha1(rand()),0,8);
	   
	   //encriptamos la contraseña para evitar que un ataque a la base de datos pueda conseguirlas
   	   $pass2=sha1($pass);
		
	   //grabamos la nueva contraseña en la base de datos
	   mysql_query("UPDATE clientes SET password = '$pass2' WHERE nickname = '$nickname' ");
	   
	   //Definimos el mensaje que enviaremos al usuario para notificarle de su nuevo password
	   $cuerpo= "Hola $nickname, aqui tienes tu nuevo password para poder acceder a la Tienda Virtual: $pass";
	   $cuerpo .= "<br> Si lo deseas podras modificarlo accediendo a tu perfil dentro del sistema";
	   $remite= "Mi nombre de remite";
	   $asunto= "Nuevo password para acceder al sistema";
   
	   enviarcorreo($email,$nickname,$cuerpo,$remite,$asunto);  //Funcion creada por mi para enviar un correo por medio de phpmailer
		
	   conectar(0);
	}
  
Gracias por vuestra ayuda!