Bueno, tienes 2 opciones:
1.- Hacer el campo nick como 'unico' en la base de datos. En ese caso, al intentar un update con un valor que exista en otro registro la consulta producira un error. Asi que seria cuestion de mirar si mysql_query() devuelve false (error en MySQL) y comprobar el numero de error con mysql_errn() (
www.php.net/mysql_errn) que corresponda con campo unico duplicado y en ese caso mostrar el mensaje.
2.- El metodo facil: realiza un select por ese nick antes del update. Si devuelve un registro es que ya existe y mandas el mensaje. Eso si, siempre y cuando el usuario no quiera cambiar su nick por su nick actual. Si, es un contrasentido, pero siempre habra algun lumbreras que en el campo nick para modificar ponga el valor actual.
Saludos.