I have a plastic bottle filled with drinking water where only one side of the bottle has air bubbles. I know that water is not pure and there are dissolved gases, and my theory is that there are small microscopic holes on one side of the plastic bottle that make bubble formation possible. Or may be its a temperature difference between the two sides (which shouldn't be the case - the bottle was kept in room temperature, but it was closed for a day or more). What could be the cause?
Your reasoning seems good. A number of things can affect nucleation of bubbles, such as surface defects, which you state, as well as temperature (was one side of the bottle facing the sun, perhaps?), and even sound.
A fun demonstration is to put a cup of carbonated beverage in an ultrasonic bath (e.g. parts cleaner or humidifier). Here, cavitation serves to nucleate bubbles.