Don't forget you can only use the restore media that came with your Mac, i.e. you can't use an iMac restore DVD to restore a Mac mini, especially if its an Intel iMac's media.
You could also try putting the DVD in your Mac mini, restart, as soon as you hear the chime, hold down the option key. (The one to the left of the Command key (the one with the Apple on it)) Keep it held down until you see a boot screen similar to the one below. Note the Windows partition won't show on a G4 Mac mini (this was all I could find on images.google.com) but instead should show a CD icon.
If it doesn't work, then perhaps try booting the media on another computer (yes it will complain that it won't work on this model of the Mac but at least you know the media isn't hosed). If you have another G4 or G5 Mac, try starting the Mac mini up in Target Disk Mode with a firewire cable connected between the two and doing a remote install?
Hope some of this helps
pac