Circular dependency in Ubuntu Release upgrade

I had exactly the same problem after upgrading a server from 14.10 to 15.04 yesterday. I solved it with these commands:

sudo apt-get remove keyboard-configuration
sudo apt-get install keyboard-configuration
sudo apt-get update && sudo apt-get upgrade