720 x 480 is SD, not HD. So you start with SD material, and then export to a very lossy codec, maybe without the proper bitrate. No surprises yet.
Premiere Pro is a professional application designed for professional use. To get the most out of it with the least difficulty, I very strongly recommend one have some basic education in video production before trying to use software at this level. For those unwilling to dedicate the time and money to such a proposition, there are a plethora of consumer editing programs out there that will probably be easier to use and offer less hassle. The Tools section of VideoHelp.com is a good resource for such programs.
Correction. I meant to say 1280x720 and it looks like 720x480 on output, but
I think I have it sorted now. I chose to buy Prem cs5 because it is one of
the best. I have used FC Pro for a number of years.
What was your solution? It could help someone else later on.