I think @Killercam is right, I'll try to explain the same thing a little more elaborately.
Firstly. in the case considered, since the fluid and the cylinder is chosen, increase in velocity directly translates to increase in the Reynolds number as $R_e = \frac{\rho V D}{\mu}$.
Before considering flow in the range $250 < R_e < 2\times 10^5$ , lets first observe what happens in the region where the viscous force dominates over inertial forces i.e $R_e <<1$. The fluid slowly "crawls" over the surface of the cylinder. There are 2 stagnation points on the leftmost and rightmost parts of the cylinder.

From the solution for inviscid flow over cylinder (superposition) we can note that tangential velocity is maximum at mid-section and decreases as and decreases as we proceed "downhill"
This can be extended to viscous flow and two important things are to be noted here:
- The shear stress is maximum at the mid-section, which is implicit as a higher velocity gradient is created because of the larger value of tangential velocity.
- The static pressure starts to increase after the mid-section. i.e the pressure is increasing in the direction of flow $\frac{\partial P}{\partial x}>0$ which is called as an adverse pressure gradient
As $R_e$ is increased (i.e velocity is increased), the inertial forces start to dominate over viscous forces.The flow velocity is zero at the surface and the particles very close to the boundary have a very low momentum since they experience very strong viscous forces. On the right part of the cylinder, the fluid particles close to the cylinder not only experience strong viscous force, but also adverse pressure gradient which eventually forces the fluid particles to stop/reversed, causing the neighboring particles o move away from the surface. This is called as flow separation. It results in the creation of a free shear layer which ultimately rolls up to form a vortex.
@Killercam said:
The velocity of the flow divided by the diameter of the cylinder is the typical crossing time of the fluid, hence is directly related to the frequency of the observed oscillations for a specific Reynolds number.
After a vortex is shed, the fluid particles behind have to undergo the same process i.e it takes the same distance to come to rest and then causing the neighboring particles to separate. Since this distance is a small part of the cylinder, $dist \propto D$ and hence the time interval between 2 vortices shed from the same side(top/bottom) of the cylinder $time \propto \frac{dist}{V}$ i.e $time \propto \frac{D}{V}$.
The time interval is exactly the time period of vortex shedding and hence the frequency of shedding is
$f=\frac{1}{T}\propto \frac{V}{D}$