Issues installing MySQL server on Ubuntu 13.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.