ok, so when you turn on your system after 15 - 30 seconds the msg appears to the top right hand side of the xmb... and the system blows cold / cool air out from the vents at the back? >> i already know the answer, had the same a few months back. you need to replace the thermal paste
below the heatspreaders. you have already changed the paste between spreaders and heatsinks yes?.. the reason it will blow cold air and still say its overheating is because the heat is STILL on the gpu/cpu chips so the sensors will pick up instantly and shut down to prevent damage.
cpu/gpu heats up, heat is transferred to the heatspreaders via thermal paste, and then further transferred from the spreaders to the heatsink again via thermal paste, then on to the fan and sent into the atmosphere. hope this helps buddy. need any help just ask.
and scrap the shims and the fan mod, they will only shorten your ps3's life. the shims are pointless, just another way for ppl to make money on obvious console faults, with even more obvious solutions,
copper shims >> need to use x2 as much paste (both sides) they can only conduct the heat that is supplied to them > so its all on the paste itself
fan mod. pointless, the increase in fan speed indicates a possible problem. its there for a reason... full speed is not gonna fix future faults, or keep it cooler... again its all on the paste