If I remember correctly - RedHat switched from Aladdin ghostscript to GNU ghostscript from 7.1 to 7.2. When I gave 7.2 a test drive I could not get it to print postscript to an HP printer. This was several months ago. I ended up uninstalling all the 7.2 printing utilities and installing the utilities from 6.2 - and everything worked. It's a solution that saved me a lot of time. Rip out ghostscript, lpd, the print filters, and set up utilities and put the old RPMS's that worked you earlier for a quick solution. Then when you have some time - you can try to get the latest version working after you have gotten your real work done. That is why I have become wary of RedHat lately - in their desire to ship the latest and greatest and keep up with Suse and Mandrake etal in the distro wars - sometimes things are not ready for production environments - if it were a .0 release - maybe.... but not in the third iteration! Good Luck!
My printer setup has gone south as a result of the upgrade from 7.1 to 7.2 at the install fest. I need help because I have real work to do and no time...
Generic canned answer - have you applied all updates? There have been quite a few updates that went by for printing in particular.