Comment 15 for bug 881079

Your rcS.d shows symlinks for /etc/init.d/keymap.sh and /etc/init.d/console-screen.sh, neither of which is part of a standard Ubuntu install; they come from the packages 'console-common' and 'console-tools' respectively. These may be slowing down the boot, or even interfering with the console configuration by the console-setup package which owns this. (The console-tools package is being obsoleted in both Debian and Ubuntu, but nothing so far is taking care of forcing its removal from disk.)

Could you please run 'sudo rm /etc/rcS.d/S05keymap.sh /etc/rcS.d/S90console-screen.sh' and reboot, and see if that corrects the problem for you?