with the disk in, start up, press and hold C (just C, not option-C, not ctrl-C, just plain o' C)
... is that what you did?
if not, try that
if so, after everything stops (aka, waiting for user input), there's the menu up top, is that where you found disk utilities?