In one of my moves I was given this code by the host and have been using it pretty much ever since. Not sure how big you are, but give it a shot.
Download your current database as a .sql file and then upload it to the new host.
Make your new database/user/password at your new host.
Copy and paste this code into notepad or something and save it as import.php or whatever you want. Edit it as needed with your username/pass and file paths.Upload that to the server and run it
www.yoursite.com/import.php It will take a while, but it should import the .sql into your database.
Code:
<?PHP
$TheFile = "/home/user/public_html/foldername/filename.sql";
$User = "mysqluser"; // NOTE: Either use a MySQL user or your CPanel/Netadmin user
$Password = "mysqlpass";
$DatabaseName = "mysqldatabase"; // NOTE: The database is prefixed with your CPanel/Netadmin user
$Results = shell_exec( "mysql -u$User -p$Password -hlocalhost $DatabaseName < $TheFile" );
echo "Results from MySQL import of $DatabaseName with User $User with file $TheFile:\r\n $Results\r\n";
?>