Weird. It should have no problem booting to a retail OS 9.1 Install CD.
Have you another Mac capable of booting to the retail OS 9.1 Install CD? If so, that would be a good way to verify the CD.
It would also allow trying plan C. That is, to install a Universal (boot any Mac) install of OS 9.1 on a firewire drive, then try booting the Cube from that. To perform a Universal install of OS 9 -
1) Boot to the CD, then run the OS installer. Step through the pages in the installer (choosing the correct destination volume in the process) until you get to the "Install Software" page, the page with the "Start" button on it. Don't click that button.
2) Click the "Customize" button at the bottom left of the page.
3) On the new page, click the pulldown menu to the right of "Mac OS 9.1", and select "Customized Installation..." from the list offered.
4) On the next new page, at the top is another pulldown menu labelled "Selection:" - click that menu and select "Universal Installation".
5) OK that page, then click the "Start" button.
This will produce an install that is capable of booting any Mac for which that OS 9 version is valid.