my brother had this problem when going from a 1080p Tv to a 1080i one...

As 1080p has a proper setting on the outfeed the 1080i max resolution wasn't picking it up.

he got round it by phoning me up and i went through the settings to sense the new outfeed.. He had a black screen infront of him but the menu was there just not being shown....He needed to tell the PS3 to change the output video HDMI settings... So when booting up it was...

left x 7

down x 10

enter x 2

right

right

Then it will search for display properties and fingers crossed pair with the TV

give it a shot