the heater can work a little strangely when it begins to fail. Also possible that the coolant sensor connector has a frayed wire causing a partial connection -- a common issue with that connector over time.
I'd still verify there's no air in your radiator (as posted below)... - Have you had a coolant flush lately? Also just verify the level of the coolant fluid in the radiator (could be low)...