Does it take that long if the game console is connected with any other input?
If not, you might try changing the settings or trying a different HDMI (v1.3 rated) cable.
Or, if you're running it through the receiver, try connecting it directly to the TV to see if that helps.
Just got a PS3 and am having issues. For quite some time, my cable box (connected via HDMI) would take up to 3-5 minutes to negotiate and give me picture when the cable box was set to an HD channel. Frustrating, but I put up with it. Once it negotiated, I could change channels from HD to non HD and back with no issues - it was only when starting up. I also have a Mac Mini hooked up via HDMI and that causes me no issues whatsoever.
I had a Sony BlueRay player (via HDMI) that also worked fine. However, when I got the PS3, I disconnected the BlueRay and used that HDMI to connect to the PS3. When I power the PS3 on, I get the Initial Setup screen, it asks for the language, I choose English. It then states "An available HDMI device was detected. Do you want to output video and audio using HDMI?" I choose Yes, and my screen goes black, the receiver and TV show "No Signal" - after about 20 seconds, it pops back up asking me for the PS3 Language choice again, and the whole process repeats. I've tried resetting the PS3 several times, have reset the Onkyo 606...any ideas??