MySQL Workbench (free as in beer, free as in speech) has dump and restore features.
http://dev.mysql.com/doc/workbench/en/wb-manage-server-data-dump-tab.html
Phpmyadmin and other admin tools also have those features, but web-based tools may not handle such a large table properly.
Dump your big table from your old server to a file on your desktop machine. Restore it to the new server. It may take overnight. So what? You only have to do it once (unless you mess it up the first time). Side benefit: you'll have a backup of your old table that you can put onto a DVD-RW and throw in your desk drawer.
You might have to segment the dump process by selecting rows a few million at a time. That's probably a good idea, because then you can restart the process if it crashes.
There are some tools (sqlyog) that can copy data from one server to another directly, as well.
Happy data wrangling.