Mysql – Installing MySQL server 4.1 on Ubuntu 11.04

Assuming this isn't an Internet connection issue ("Connection failed" is a needlessly obscure message), then this looks like a problem with the particular Ubuntu mirrors your system is trying to use, rather than something specific to MySQL.

The answer posted on What to try when apt-get install xxx Results in Connection Failed seems like it should get you pointed in the correct direction to resolve this.

It's also possible that sudo apt-get update might fix your problem now, even if it didn't fix your problem before, since some time has passed. I'm speculating, but it could be that if the information fetched by the update operation causes your system behave differently when it's trying to fetch the files you're needing to install, that might also resolve the problem.

Please read this but report:

http://bugs.mysql.com/bug.php?id=69027

The workaround ("solution", really) to this is to change the password for the affected user to a post-4.1 hash. This is really a recommended best practice, regardless - password hashing and authorization process prior to 4.1 has notable security limitations (discussed in documentation at http://dev.mysql.com/doc/refman/5.0/en/password-hashing.html). Restoring a 4.1 version of the mysql schema on to a 5.6 server is a bad idea at any rate, because 5.6 has additional columns in some tables and some completely new tables, which may or may not be missing now depending on how you configured mysqldump when you created the dump file. You may have caused other problems that you may not see immediately.

Also, specify skip-secure-auth option in [mysqld] section of my.cnf/my.ini file of your MySQL server and restart it.