Random/unexpected out of memory during texture allocation

Gaming and Visualization Technologies APIs OpenGL
1

I am using the following code to upload my textures on the GPU in a loop before starting to render but I get some ‘random’ out of memory error returned by glTexStorage2D. I mean that sometimes a smaller texture return out of memory but the next one, a bigger one returns ok. I checked with GPU-Z and only 180MB of the video card memory (1GB) is used. I also used Gdebugger and there is not much memory used (VBOs, Front/Back buffers, Textures, Shaders). The textures are between 32x32 to 2048x2048. The textures that do load display correctly.

glGenTextures(1, &TextureID);
showGlError();
glBindTexture(GL_TEXTURE_2D, TextureID);
showGlError();

Nof_MipMap = 2;

glTexStorage2D(
GL_TEXTURE_2D,
Nof_MipMap,
GL_RGBA8,
Image_Width, Image_Height);
glError = showGlError();

glTexSubImage2D(
GL_TEXTURE_2D,
0,
0, 0,
Image_Width, Image_Height,
GL_RGB,
GL_UNSIGNED_SHORT_5_6_5_REV,
Image_Address);
glError = showGlError();

glGenerateMipmap(GL_TEXTURE_2D); //Generate num_mipmaps number of mipmaps here.
glError = showGlError();

glTexParameteri( GL_TEXTURE_2D, GL_TEXTURE_WRAP_S, GL_REPEAT );
showGlError();
glTexParameteri( GL_TEXTURE_2D, GL_TEXTURE_WRAP_T, GL_REPEAT );
showGlError();
glTexParameteri( GL_TEXTURE_2D, GL_TEXTURE_MIN_FILTER, GL_LINEAR_MIPMAP_LINEAR );
showGlError();
glTexParameteri( GL_TEXTURE_2D, GL_TEXTURE_MAG_FILTER, GL_LINEAR );
showGlError();