I'm not an expert in Colorado finance law, but what you described is consistent with what I'd expect from my background in retail, especially retail when crossing the "online" to "in store" border.
Stores typically have a choice of two options for how to handle this kind of exchange. They can handle it as a true "even exchange", where they just swap a box for another box and don't assign any dollar value to the transaction; or they can accept a return, and then process a sale using that return as the "funds". It seems like the latter is what they really did.
When accepting a return from an online purchase, though, I see even exchanges very rarely if ever. Many companies keep their online business separate from their in store business - sometimes technically a different company, in fact, but usually at least it's quite a bit separated. One common consequence of that is that, while stores will usually accept returns from the online version, they don't treat it as a return from an "in store" purchase - they treat it differently, and one result is something like this; they refund you the paid sales tax and then re-sell you the new item, at their own sales tax rate.
It does seem like they could have chosen to rung it this way - see the Colorado Sales Tax Guide, Part 3:
Under certain conditions, the fair market value of tangible personal property exchanged by the purchaser as part of a taxable sale is excluded from the taxable purchase price. The fair market value of the tangible personal property exchanged by the purchaser is excluded from the taxable purchase price, if either:
such exchanged property is to be sold thereafter in the usual course of the retailer's business; ...
However, it doesn't surprise me that they didn't.
Separately, it is correct that the online site charged one rate (the rate applicable to your home), and the store charged a different rate (the rate applicable to the store's location). Colorado uses destination source tax rates; basically, that means charge the tax appropriate for the delivery destination (for deliveries) and the rate for the store's location for in-store purchases. See Part 1 of the guide above for more details.
