I'm assuming that you're utterly locked out of your box, otherwise you could just do:
$ sudo passwd root
[sudo] password for yourusername: type-your-pass-here
New password: type new root pass here
OK, so you're booting and you're at the grub menu. Do a quick down & up arrow to stop the automatic countdown clock. Next, just type init=/bin/bash or arrow down to repair mode (which is actually single-user mode). That is the kernel line. (You might have to tab to get down to the edit line... can't exactly recall since I'm not going to reboot just to double check).
This will bring the system up in single user mode. There you can type:
$ passwd root
New password: .....
When you've finished, exit the shell (^D or exit), and the boot process will complete.
A side note.... You really shouldn't have to set a root password on your machine. Just log in as the main user (the one you supplied when you installed ubuntu) and type sudo -i at your command prompt, and voila you become root.
rw init=/bin/bash, are you hittingEnterthen pressingbto boot? – unpythonic Jul 02 '11 at 01:00