I've upgraded from Gutsy to Hard (8.04), and my Tex Gyre fonts still work with Latex. Have you tried creating a sample document using Tex Gyre fonts?
To check if they are currently available on your system, try using the "updmap" command. Here's the output on my system (the q*.map files correspond to the Tex Gyre fonts):
# updmap --listmaps | grep "Map q.*"
updmap: This is updmap, version 1167072206
updmap: using transcript file `/root/.texmf-var/web2c/updmap.log'
More information about formatting options