The cables connecting the different sources to the receiver are overpriced monster cables (high-speed gold plated, <1m) I got them with the TV... I should sue Monster Cable if they're not good enough
Only the one connecting the laptop to the receiver is a Belkin DVI-HDMI cable, with an Apple MiniDisplay-DVI converter thingy.
The cable connecting the TV with the receiver might be a cheap one, I don't know because I haven't bought it myself (it was new though). I can't switch with different cables easily because of the length (I need at least 3m to reach the TV). But I'd consider buying new ones it if there's a good chance of succes.
I have updated the firmware recently yes. It didn't help.
If I remember correctly, bringing up the Onkyo's menu doesn't take very long but switching back to one of the HDMI feeds does... I'll have to double check tonight (not at home now).
By the way I think the thread should be somewhere else, if any mod reads this feel free to move it accordingly...