Sorry if most of this is "duh" stuff, just being thorough:
1) make SURE you have the PPC distro. It's community supported and therefor not on the main page.
10.10 is here:
http://cdimage.ubuntu.com/ports/releases/10.10/release/
10.04 (LTS) is here:
http://cdimage.ubuntu.com/ports/releases/10.04/release/
Older versions: basically the same link, just replace the version number.
2) make SURE you burn the disc image properly. If you're just burning the image to the disc you're doing it wrong, it has to essentially be cloned.
Kbase article:
http://support.apple.com/kb/ht2087
3) Make sure your boot cd-rom/dvd-rom/etc is working properly. Try burning the image at a slower speed if the drive you're reading from is older than the one you're burning with, and test/make sure the drive itself works. CD-rom drives, like any other piece of hardware, do die eventually, I've had several crap out on me over the years, and G4s are old...
4) if all else fails, try the alternate images.
Also, this may be another "duh" thing, but just holding down "c" after the boot chime will boot from CD instead of hdd. Good luck!