Gas clouds with masses much higher than $10^3\,M_\odot$ are plentiful in galaxies; the typical star-forming cloud (the so-called molecular clouds) have masses of $10^3\,M_\odot$ to $10^7\,M_\odot$. When quasistars (hypothetical stars powered not by nuclear fusion, but by accretion onto a central black hole) cannot exist today, it is because all gas in the Universe has become polluted with metals.
Stars form from collapsing gas clouds. In order for a region of a cloud to collapse, it must be sufficiently dense, and sufficiently cool; if it's too dilute, there's not enough gravity, and if it's too hot, the energy of the individual atoms counteracts the collapse, making the atoms escape.
Jeans' mass
This criterion is captured in the Jeans instability equation. The relation can be expressed in several ways; one way is to say that the mass of the cloud — or a small region of it — must exceed the "Jeans mass":
$$
M_\mathrm{cloud} \gtrsim M_J \simeq 3\times10^4 \frac{T^{3/2}}{n^{1/2}}\,M_\odot,
$$
where $T$ (in $K$) and $n$ (in $\mathrm{cm}^{-3}$) are the temperature and the number density of the gas.
From this equation you see that the cooler the gas is, the smaller the threshold. In other words, the smaller stars you can form. If the gas is not able to cool, only the largest clumps will collapse, and hence such stars will be very massive.
Gas cooling
So, how does the gas cool? Hot gas means that the particles have large velocities. If the particles collide, they may excite each other, bringing an electron to a higher state at the expense of slowing down — i.e. cooling. When the electron de-excites, a photon is emitted, which may leave the system. Thus, the kinetic energy of the atoms is converted into electromagnetic energy which escapes.
However, an electron is only excited if the energy of the collision matches closely the energy needed for the excitation. If the collisional energy is too high, or too low, the atoms simply bounce off of each other, maintaining their total energy (although one may transfer some energy to the other).
The effect of metals
If the gas consists only of hydrogen and helium, there are only a few available energies for excitation. Hydrogen happens to be able to cool efficiently around $T\sim10^4\,\mathrm{K}$, while helium cools efficiently around $T\sim10^5\,\mathrm{K}$, but at other temperatures, the gas tends to stay at its given temperature.
However, as soon as there a some metals, the many electrons of these metals, with their many possible transitions, allow for atoms with many possible energies to be excited. Thus, before a gas cloud of $M\sim10^3\,M_\odot$ collapses to form a $10^3\,M_\odot$ star, it will fragment into smaller pieces, forming smaller stars.