I bought a used G5 about a month ago, and had no fan problems yet, but have you dusted the insides very thoroughly? When I brought mine home, it needed about an hour of wiping, and blowing (huh-huh) and it's still only 90% clean.
If there is a blanket of dust somewhere, it could be retaining the heat.
That, or a clean erase/install of OSX(doubtful)
I'd like to interject a related question: Has anybody ever replaced the G5 fans with quieter ones? Mine are fine, but hey, thought I'd ask. I could be up for it. Thanks