Bad Idle

Well I have a 91 GMC with a 350. When I bought the truck it had a rough idle on start up in cold weather. ( I live in MT). When the heater was on the check engine light would come on. When I turned the heater off the check engine light would go off after a bit. Well I had a brand new 350 installed by a mechanic in my truck and I still have the same problem and also now it rough idles when the motor is hot. I had the idle control replaced and nothing. Like I said the motor itself is new.