It's unfortunate because it means that you have lost all the comments, ratings, albums/organization, etc. I would ask them if they still have it.
Make a copy of the entire CPG directory with all its files before you make any chages, so that you will have something to start from again if there are any problems. If they still have the database, ask them to give you a back up file, which will let you restore the database on a new host. You won't have to do nearly as much work if you can get that file.
If you can't get the database file, you'll need to organize the images in your /albums folder. You would remove the images with thumb_ and normal_ prefixes. (Move them into a different folder for now, just in case there is a problem later.) The image files without prefixes can the be batch added and reorganized. At this point you should have two image containing folders on your computer's desktop. One should have the plain image files, and the other should have the prefixed image files. Then look in the includes folder and delete the install.lock file and the config.inc.php file. Clear the /albums and /albums/userpics directories of all the image files. Leave the index.html files. (You should have these image files stored and organized in the other folders at this point.) Then you FTP the Coppermine files to the new host, and you run install.php. This will create the new Coppermine installation. You can then use the batch add tool to start putting the pictures back into the gallery. Verify that everything is working before you get rid of that original unmodified copy of your old CPG directory.
If you can get the DB backup file, you can restore the database tables using a database tool. Then you FTP the CPG folders to the new host and make the required changed to the includes/config.inc.php file, which will contain the information you entered when you first installed Coppermine. You simply change the info here to your new host's info. This will allow Coppermine to connect to the databases, etc.