I'm not too sure what's causing your problem as you don't really describe it other than to say it's an"interlacing" problem, which doesn't actually mean anything.
What resolution were you running before you updated your video card? 720p?
You should have been able to run at least 1360 x 768 (if not 1366).
Most modern video cards don't support interlacing at all. If they did, you would be running 1080i.
If you were running 1360 x 768 before the driver
update try running it again and see if your problem is gone. If not, reset your TV to defaults and try it again. If not, roll back your video card driver and try 1360 x 768 (it's only a 6 pixel difference). If you cannot run 1360 with your old driver, you may have to contact ATI (AMD now) and explain to them what your problem is. There may be a problem with the driver they are unaware of.
You can always try the size and position settings on the TV to see if it corrects anything. Also try using the "auto" option on the TV if it has one.
Lastly, you can always try a different HDMI to DVI adapter. Make sure it has all the pins on the DVI side, and not just half of them. There are two or three different types of DVI, the best bet is always get one that's fully populated with all the pins.
Here is a good page explaining the differences: DVI Tutorial - Digital Visual Interface Tutorial - PacificCable.com - 1-800-931-3133.
Make sure you get an adapter that is the DVI-I so it will definitely have the signals the HDMI cable wants. At the very least make sure you have the DVI-D and NOT the DVI-A.
You could also try using a VGA cable with an adapter on it as most TVs come with a VGA connector (especially 720p/1080i TVs). If this corrects your problem you'll be a happy camper. This should also eliminate any overscan issues that may become apparent with HDMI connections. You should be able to pick up a VGA/DVI adapter for a couple of bucks, and a VGA cable (if you don't already have one) for under $20.
That's about all the advice I can give. I know it's not much, but I hope it helps.