All you need to do is
bzcat mybackup.sql.bz2 | mysql (parameters for mysql)
If your web host doesn't give you shell access, dump them in favour of one who does.
MySQL dumps are not bz2 or gzip normally. MySQL just dumps the output in a plain file. Moreover, the clever way MySQL does it, going from 5 to 4 should work as well provided no MySQL5 specific features were used (but the application may not work if it was designed for v5).
You say "You tried manually"?
The only correct way of importing a mysql dump is putting it into the CLI mysql tool. Nothing else, including pasting, using phpmyadmin (which is a useless piece of junk), etc, will get it right, so don't bother.
Mark