I recently upgraded my Pokémon storage to hold more Pokémon. After doing so, I noticed the CP on my Pokémon changed - some are better, some are worse. What happened?
It actually had nothing to do with you upgrading your storage. The way CP is calculated has been adjusted and it is now reflected in-game.
See this announcement:
We have made adjustments to the CP (Combat Power) of various Pokémon. Some Pokémon, such as Alakazam, Rhydon, and Gengar will have their CP increased. Others will have their CP lowered. These changes will allow a more balanced and competitive battling and training experience in Gyms. We will continue to adjust the CP going forward to improve the game balance when necessary.
With the version 0.47 update, the formula to compute base stats has changed. Base stats are used in the formula to compute CP. Hence, all CP values are changed. Find more details from Understanding the Pokemon Stats Update.