I have had some weird issues with ATIs in the past. I had a 9600xt that if it ever cooled off it would give me garbled text for 20 minutes until it got warmed up. So if the pc was shutdown you would have to wait like 20 minutes before you could see the display.

As mentioned check connectors and everything else.