Ok, so it's definitely compressed and it sounds like the new server is trying to decompress it but might not be doing it properly. If you do decompress it locally then it might end up being too large to actually upload it.
Does your new hosting come with SSH access or is it FTP only. If it's FTP only what you might do is get in touch with them and tell them you have a compressed sql dump that you're having some issues getting moved to their server and see if they can assist. Many hosts will have you ftp it to the server and they'll import it for you.
If your hosting happens to have SSH access as well, then we could give some assistance on importing it through SSH.
