You should have console access to your physical machine such KVM,IPMI..etc.,
At the grub prompt press e to enter edit mode.
Select the second line press e again.
At the end of a similar entry, Your Grub entry will probablly not look the same as this.
kernel /vmlinuz-2.6.18-308.4.1.el5 ro root=/dev/sda3
Add init=/bin/sh (The steps so far should work on Debian/Ubuntu servers although with Ubuntu you might need to use /bin/bash instead of /bin/sh)
kernel /vmlinuz-2.6.18-308.4.1.el5 ro root=/dev/sda3 init=/bin/sh
Now press the enter key and then b to boot.
This will take you into single user mode.
Now mount the root partition in read and write mode so that the changes can be commited.
# mount -o remount,rw /
Once the file system is mounted type the following.
# passwd root
You will prompted for the new password and then to confirm.
Job done reboot.
