Alright, here's the lowdown.
I got this box:
http://www.amazon.com/HDMl-Composite-S-Video-Converter-Adapter/dp/B0047PDBP0/ref=sr_1_7?s=electronics&ie=UTF8&qid=1296766437&sr=1-7
When I finally got everything working the picture was in black and white
After checking connections, I checked the converter box and found that pal output was selected. I changed it to ntsc and the color came back, but the screen was all squashed.
I tried a few different resolutions and no help, on the 4:3 resolutions, I had black bars on the left and right side.
From there I installed the ATI catalyst drivers and found I could scale the display to fill the screen. Now my screen looks great and everything works perfectly.
I haven't yet tried blu-ray or dvds, but I suspect they'll be just fine.
Anyways, thought this might be interesting to some.