Jeff,
Aaron Erickson and Daryl Richardson's advice sounds pretty good.
We fixed a problem like this a few years ago -- PT deck over small columns. In that case the original design was marginal for shear, and then they lost a number of strands over the column head to corrosion.
A co-worker designed conical caps to be poured around the tops of the columns, using the references Aaron cites. The issues we had were:
1. When roughening the bonding surface on the column, how rough is rough enough? If I had it to do over again, I would sawcut about 1/2" near bottom of cap and chip out a band at least 4 to 6" tall as a key. Depending on how badly the deck is evidencing a punch failure, it might be a good idea to shore before you start taking the column apart. You might even want to try jack it back up if it has really started to punch. Then epoxy infect the punch zone.
2. How to get a continuous ring of reinforcing around the column. If I had it to do over again, I would use a #3 spiral with a lot of turns. The ironworkers would have to wind it onto the column like putting a key on a split keyring, but it can be done. I like this better than an external ring of steel, because at least around here, we want any steel in a parking ramp to be buried in concrete due to constant infusion of de-icing salt.
3. The cap had to be poured about 4" below the bottom of deck, then grouted with non-shrink grout. I think we used a dimension of 3", and it made the contractor's life difficult getting them poured. If I remember, we used a pea-gravel mix, maybe 6000 psi.
Anyhow, for all that, the repairs worked very well and actually looked great. The contractor had stainless steel conical forms made, which were a large part of why they looked so good. (Then Halloween came and vandals stole half of them for scrap. The contractor was understandably really, really mad.)
Good luck,
Mike Hemstad, P.E., S.E.
Meyer Borgman Johnson
Minneapolis, Minnesota