One of the major challenges for in vivo, micro-computed tomography (CT) imaging is poor soft tissue contrast. To increase contrast, exogenous contrast agents can be used as imaging probes. Combining these probes with a photon counting x-ray detector (PCXD) allows energy-sensitive CT and probe material decomposition from a series of images associated with different x-ray energies. We have implemented full-spectrum micro-CT using a PCXD and 2 keV energy sampling. We then decomposed multiple k-edge contrast materials present in an object (iodine, barium, and gadolinium) from water. Since the energy bins were quite narrow, the projection data was very noisy. This noise and further spectral distortions amplify errors in post-reconstruction material decompositions. Here, we propose and demonstrate a novel post-reconstruction denoising scheme which jointly enforces local and global gradient sparsity constraints, improving the contrast-to-noise ratio in full-spectrum micro-CT data and resultant material decompositions. We performed experiments using both calibration phantoms and ex vivo mouse data. Denoising increased the material contrast-to-noise ratio by an average of 13 times relative to filtered backprojection reconstructions. The relative decomposition error after denoising was 21%. To further improve material decomposition accuracy in future work, we also developed a model of the spectral distortions caused by PCXD imaging using known spectra from radioactive isotopes (109Cd, 133Ba). In future work, we plan to combine this model with the proposed denoising algorithm, enabling material decomposition with higher sensitivity and accuracy.