During weight loss, triglycerides which are composed of carbon, hydrogen and oxygen, are broken down. During respiration, the inhaled $O_2$ is bonded to a carbon atom to form $CO_2$ which we exhale. However this process happens anyway, even one isn’t trying to lose weight. So that suggests to me that during weight loss people must inhale more oxygen, otherwise where are all those extra carbon atoms that we now have going?
First one needs to make it clear that oxidation of foodstuffs, either those in the diet or from deposited reserves, occurs in order to generate energy (ATP) for life’s processes — the most evident to the non-biochemist being to perform muscular work. So, as the poster correctly implies, this will occur in both fasting and non-fasting individuals, and the fairest comparison would be between the same individual performing the same amount of energy-requiring processes.
Let us consider this comparison in the simplest situation where the person “losing weight” is fasting, i.e. has no food intake (rather than being on some fancy diet). After his glycogen has been depleted, the fasting individual will be producing all the energy for his various needs by oxidizing triglycerides that had been deposited previously in his fat cells. The amount of oxygen he inhales (assuming this is strictly related to requirement — I’m not a physiologist, so I don't know) will be that required to oxidize the triglycerides to produce this required energy.
Now compare this to the same individual, not fasting. His energy needs have been assumed to be the same as in the fasting state, but he is generating this energy from his food intake. Making the unlikely assumption for comparison that this were all triglyceride, the amount of oxygen needed to oxidize this would be exactly the same as the fasting individual.
I think that deals with the fallacy in the question, perhaps caused by not reflecting on what the oxygen inhaled by the non-fasting individual is used for. Technically one should admit that if the simplistic assumptions do not hold, the strict equivalence would not either. Different foodstuffs (carbohydrates, fats, proteins) are in different oxidation states, so the amount of oxygen required to oxidize them in the fed individual would depend on diet. If the food intake of the fed individual were greater than his needs and he was depositing glycogen or fat, extra ATP would be required to do this, which would likely be generated by oxidative phosphorylation. No doubt one can think of other possibilities, but these were not the focus of the question.