Unable to correct problems, you have held broken packages

That particular error message may indicate that you have held packages, but it may also indicate a different problem.

You can get a list of actual held packages with:

dpkg --get-selections | grep hold

If there are none, or none look related, then it's probably something else. Check carefully the output of the command you were trying when you got the error message, as there may be other clues in the full output from that command, aside from the error message.

Another method of troubleshooting may be to use aptitude rather than apt-get to try to install your package:

sudo aptitude install <packagename>

Aptitude will give up less easily and will attempt to find solutions that may involve modifying other packages. It may give you more explanation of the problem and options for fixing it.

Occasionally aptitude will be too eager to remove or downgrade large numbers of packages to satisfy your request, in which case retrying with -f changes its priorities and helps it come up with solutions that involve removing/downgrading fewer packages even if it means not all changes you requested can go ahead:

sudo aptitude -f install <packagename>

Edit: this is an old answer, and since it was written a newer APT front end, simply titled apt, has become the preferred command line APT interface for end-users. It is still not the Swiss army knife that aptitude is, but it's a bit more human-oriented than apt-get. I haven't taken the time to investigate how it would help in the above scenario, but it's worth using.

That happened to me too. All I did was sudo apt-get update and that fixed my issue. Good luck.