How to fix apt-get upgrade/install fail error related to linux-headers-server unmet dependencies

I was trying to upgrade my Ubuntu server and got this error this morning:

You might want to run 'apt-get -f install' to correct these.
The following packages have unmet dependencies:
 linux-server : Depends: linux-image-server (= but is installed
                Depends: linux-headers-server (= but is installed
E: Unmet dependencies. Try using -f.

I ran the apt-get -f install command over and over but It kept failing. Then I found the solution:

$ sudo aptitude install linux-headers-server

aptitude is smarter at dependency solutions than apt-get. It fixed the issue and the server is fine now.