If it's a large database, I don't know how well PHPMyAdmin will do with dumping it. I would do it using telnet if I was you. Just dump it to a directory, then copy it to your new server and recreate it there.
Looking.... I just found it. Here is a detailed page on how to move a MySQL database from one server to another:
http://www.vbulletin.com/manual/movingservers.html