So the process sounds correct. The error you list looks to me to have come from an installation rather than an upgrade. You'll need to drop the database from your new server, recreate it, and then load in the backup again to get back to a clean slate.
I presume you're then looking at an error 500 screen? When you access the new server, you shouldn't be getting a 500. That's the first thing you need to address.
Are you certain the filesystem permissions are correct on the library? If so, try manually updating the library path in the database to the new value.
UPDATE setting set value="/fully/qualified/path/to/your/existing/library/" where setting="LIBRARY_LOCATION";
Be sure to give a fully qualified path, and that there's a trailing slash on the end.
Does that clear the 500 error and show you the login screen? If so, you should then be able to login and start the upgrade process. If you see the installer, then your settings.php file is in the wrong place, or contains the wrong information for the database.