Is it just when you start or all the time? My truck does it when I start it after the block heater has been plugged in. One of the guys I work with said that was because of the heating with out flowing, but all I know is that it does not do it during the summer. My other guess is have you ever changed/backflushed the cooling system? My father never did and his chevy had the same symptoms and the heater core had scale build-up so tight we could hardly get anything to flow through it.
just my . 02 worth of ideas on it
Troy