My input is good and bad, I have seen the behavior you refer to in 2 different 350z's that is the overheating and the cold air in the cabin when the engine is hot and heater set to hot.
on 1 it was an air lock and it was a real PITA to get it out we ended up lifting the front of the car on ramps adding a coke bottle with the bottom cut out to the rad filler to increase height and act as a funnel/reservoir (you must block the overflow pipe and make sure the bottle is sealed to the rad) then running the engine until hot - few bubbles let it cool - same again after about a days work and numerous repeats of that it eventually gave up a big bubble of air - we refilled to correct levels and the problem never came back.
Bad news on the other it was a blown head gasket we actually think that this was due to the previous garage reusing the gaskets after some work on the heads, we confirmed it with one of those type of kits as linked to above replaced the head gasket and all was well.
As a site note we ran the 350 that had the blown gasket with no thermostat in for a while (trying to find the fault) the problem does not go away completely but it did reduce so although I hope its only an air lock I would definitely test for a blown head gasket.
Hope it helps
K