Honestly, I would try exporting at 720×480 uncompressed and look at the result, if you do see any loss of quality at all, then there’s a problem ;).
Now, anytime you scale down, Premiere has to lose some pixels, and maybe it has an issue with that certain footage, although I haven’t experienced any issues myself.
You could also try exporting at the same frame size and let your other converter do the frame downsizing and see if that helps.
Cheers,
Vince