Comment 12 for bug 398646

Christian: It is, I would say, a correct kind of answer :)

You will need to get the very latest updates (sudo apt-get update) and then install them (sudo apt-get upgrade). Doing this will install a very very new version of update-motd which does not have this bug. Did you try this? It worked for me.

If you did that, today, and it still fails to install, what does

  sudo apt-get -s upgrade -V

output? Especially, what version of update-motd does it say it would install?

Worst case, if you are still having issues, you might want to try

  sudo apt-get update
  sudo apt-get purge update-motd
  sudo apt-get install update-motd

although I can't see why you'd need to do it that way.