Lance:
I definitely had that problem in the A-36 when very high or when it was cold at altitude. The A-36 has a manifold heat system that wraps the exhaust stack. When below -10C, the front seat occupants were O.K. but folks in the rear got very cold. I did a couple of things to assist: Check for any air leaks or air coming in through the back panel behind the rear seats. Have someone get back there while it's cold and check. If no leaks, make sure the heater vents are operating correctly: mine was not flowing to max potential. When operating the engine, LOP will produce hotter EGTs which will produce the most heat into the system.
I discussed this with the Gami folks and they have an after market upgrade that produces more heat if you fly high a lot. It could be worth checking.
Hate to say it, but this is another reason I went to the twin. The Janitrol heater actually burns avgas from the left main of the Baron and will run you out of the plane if you set it for max heat. Also, these planes just weren't made to deal with all the elements at high altitude--at least the A-36 wasn't. The after market upgrades will help as will getting the best performance out of the existing system, but you are pushing the envelope.
The pressurized single or twin has a sealed cabin which elimates all outside air unless you allow it in. As some point, if you fly high a lot and in cold or hot weather, the pressurized plane with better heating and airconditioning will perform substantially better. I haven't run the heater in the P-Baron yet other than to test it. Even at 0 C, I sometimes have to run the air conditioner to keep cool.
I know everyone can't go to a pressurized plane, but there are limitations on what the unpressurized plane can do because you are just exceeding design limitations. When it gets real cold out, even the heat transfer through the rear plexiglass can be substantial.
Best,
Dave
Baron 322KS