joemarch,
I've seen many steel columns encased in concrete for fire protection requirements in parking garages. If this is in a situation where there will be lots of outside air-moisture, or where moisture may be dropping down from above, what usually happens is that the moisture gets in between the steel and concrete and initiates some surface rusting - with the resulting expansion, you end up with longitudinal cracks in the encasement and eventually chunks falling off.
Most of the "bad" conditions I've seen have no reiforcement at all so by adding some nominal rebar and ties you will probably keep the concrete fairly intact. If you are not in a moisture prone environment I wouldn't worry about it as long as you do reinforce it as you've stated.
Just remaining is the issue of cost which other members have implied above.