Comment 23 for bug 873468

We're never going to know with certainty what the cause of the failure is, but we should be providing better guidance to users about *probable* causes for the bug rather than leaving them with an opaque error message. Mirror unavailability is a very likely cause for this error.

How about:

"After updating your packaging information, the essential package '%s' could not be located. This may be because you have no official mirrors listed in your software sources, or because of excessive load on the mirror
you are using. See /etc/apt/sources.list for the current list of configured software sources.

In the case that the mirror is overloaded, you may want to try the upgrade again later.