Does mysql have a option to export the database for different version of mysql? I don't think they have software able to do what your asking though. Why is this "new" web host useing a old version of mysql? Could you just ask them to upgrade to the newer version. Just think an older version of mysql has all the security bugs already published to the web for everyone to exploit.
Late releases of phpMyAdmin may have this functionality as well.
The new host may have some reason to use 4.0.x instead of 4.1.x--it really doesn't have any to do with security, as 4.0.x still gets security updates. If anything, the old host may have more security vulnerabilities as they are 2 versions out of date (running 4.1.13 vs 4.1.15) compared to the new one, being 1 version out of date (running 4.0.25 vs 4.0.26).
Hmmmm, What do you transfer the database with? I sometimes use cPanel's backup feature. I just open the tar and get take the text out of the file. Then add in the text (which is MySQL Queries) to phpMyAdmin. Click Add and you done