Lost Linux root password - Recovery mode and init=/bin/bash fail
If you're already rebooting, just boot into the Live CD, chroot into the server's root filesystem, and run passwd. Problem solved.
I just tried on a near-blank Ubuntu server 12.04 in Virtualbox. Holding SHIFT down while booting, choosing the first entry, pressin "e" to edit, I replace
ro quiet
with
rw nosplash boot=/bin/bash
and it boots up without problems into a bash-shell. Perhaps the graphic-cards is making you trouble, thus the nosplash.