Video scaler
Check out the products from DVDO, I think that most are in the $1K range.
http://www.dvdo.com/pro/index.php
Also, you might consider a receiver like the Yamaha RX-V2600 which will upscale all analog inputs to 1080i or 720p.
With the HDMI standard in constant flux, I would consider holding off on a $1K+ video scaller purchase for a year until HDMI 1.3 has been finalized and HD-DVD and bluRay are readily available.