It's not the lack of oxygen so much as the accumulation of CO2 that we would notice first. And that would happen far sooner than we would notice the lack of oxygen, per se. (I'm addressing when the average human would experience a difference in daily life, not whether scientists would notice the atmosphere changing, something that would take very little time.)
Today, atmospheric CO2 is around 0.04% worldwide. If plants stop synthesizing CO2 into glucose (photosynthesis) and the atmospheric CO2 level rises to just 0.5%, we would notice its effect on our daily routine almost immediately.
For example, at 0.5% ambient CO2, astronauts on the ISS "experienced headaches, lethargy, mental slowness, emotional irritation, and sleep disruption" (source). At 1% CO2, we would notice our bodies reflexively trying to breathe better. We can survive CO2 levels between 1% and 2% for only about one month. We would survive for 1 week at 3.5%, and 8 hours at 4.5%. Medically, the resulting condition of too much carbon dioxide in the blood is called hypercapnia. I understand that this occurs because CO2 does not leave our bloodstream efficiently when the partial pressure of CO2 in our lungs is too high. (Chemists, feel free to correct me.)
How long would this take? A rough calculation:
Mass of atmospheric O2: 1.4 × 1018 kg O2 (Table 1)
Mass of atmospheric CO2: 1.4 × 1018 x (0.04/20.9) x (44/32) = 3.7 x 1015 kg CO2
[The line above converts current O2 mass to current CO2 mass via two ratios: their relative % of the atmosphere, and their relative molar masses.]
Annual oxygen production: 3 x 1014 kg O2 (Table 2)
One year of respirated CO2 not converted back to O2 via photosynthesis: 3 x 1014 kg O2 x (44/32) = 4.1 x 1014 kg CO2. (This is the annual increase in CO2 if there is no natural production of oxygen.)
CO2 is now 0.04% of the atmosphere. It needs to grow by a factor of 12.5x to reach 0.5%, by which point we would certainly feel the effects (see ISS astronauts above).
This requires adding 11.5 x 3.7 x 1015 = 4.25 x 1016 kg CO2 in total.
At an increase of 4.1 x 1014 kg/yr CO2, this would take 104 years.
Short answer: We would all suffer "headaches, lethargy, mental slowness, emotional irritation, and sleep disruption" no later than 104 years from now. In reality, people already experience these things after a couple of hours in closed bedrooms, offices, and meeting rooms with poor ventilation, as ambient CO2 increases, so such problems would become commonplace far sooner than a century.
So without technological intervention (say, reducing CO2 levels indoors), we would suffer serious effects even with abundant oxygen all around us.
It would be analogous to floating in a lifeboat in the middle of the Pacific: "Water, water everywhere, and not a drop to drink."