Did you happen to get the Toshiba at Wal-Mart? I have heard good things about them.
They are very good at upconverting our regular movies.
One thing that may be an option is
HD DVD to DVD9. You would have to cutout extras and foreign audio, but there would be less compression going to DVD9.
Maybe someone with more knowledge than me can chime in.