It is difficult to help because your database is in an unknown condition. Did you manage to restore it when you moved hosting? It must be done using a real restore database action it cannot be done just by importing tables. If you tried importing tables instead of doing a restore it will not work.
The way the setup system decides whether it is a new installation or an upgrade is by detecting the existence of the mp_Sites table. If the table already exists then it knows it is not a new installation, it must be an upgrade. Then it checks the mp_SchemaVersion table using stored procedures which should already be installed to find out what version it is at already so it will only run newer scripts. This is apparently where a problem is happening it cannot determine the current version so it tries running the lowest version of upgrade script that exists on disk. So my guess is that either you are missing stored procedures or missing the mp_SchemaVersion table or the user is not dbo and doesn't have permissions on the tables and procs. The first 2 issues can only happen if you did not restore it correctly. If the user (connection string user) is not dbo (database owner of the database) but he was dbo on your previous host (which he probably was) then I do not know a solution that could be prescribed in steps, it would require an expert with admin access to solve it.
When your host gives you a database and user, then you restore a database over it what happens is that the user issued by the host no longer works, he gets orphaned from the database by the restoration process and only your host can restore him. So after a restore you need your host to fix the user again.
Hope it helps,