If you are using the phpMyAdmin route, you have to make sure that your max upload/post size are set high enough in the php.ini so that if the DB file is big it actually gets fully uploaded to the host.
One alternative is to save the DB dump into a file and then manually import it into mysql through a shell, something like:
mysql -u <username> -p <password> < db.sql
Make sure that you are exporting both table structures and data from phpMyAdmin.
Another alternative, if you dare, is to just pack the database from your first host's disk and deploy it on the other host's disk, all done via the shell. Generally in Linux land, mysql stores the database into /var/lib/mysql/<db_name>.
Before doing this you should stop your mysqld so that all tables are closed and flushed.
Then you would do:
cd /var/lib/mysql
tar cvfz wordpress.tgz <db_name>
then FTP the wordpress.tgz to the other host, stop the mysqld there as well, then do:
cd /var/lib/mysql
tar xvfz <location/of/wordpress.tgz>
restart mysqld and it should all be there...data wise.
What's missing would be any special user/table permissions as they would be saved inside the "mysql" database. You could export those as single rows or what not or simply re-create them through phpMyAdmin.