This

I am using GL_LINEAR as one of the texture parameters,

+

Im also using 6 sub-regions of 1 texture

is your problem.
When using a texture atlas (put multiple sub-textures on a single texture) + using linear filtering + using exact texture coordinates, the linear filtering considers neighbor pixels at the borders. When your neighbour pixels are i.e. black, you will get an ugly line. The effect will increase with mipmapping, that is, when decreasing the screen resolution or moving father away lower mipmaps will be taken, which result in an more obviously border.

The best solution for skyboxes are cubemaps, as mhagain already said.

This

I am using GL_LINEAR as one of the texture parameters,

+

Im also using 6 sub-regions of 1 texture

is your problem.
When using a texture atlas (put multiple sub-textures on a single texture + using linear filtering + using exact texture coordinates, the linear filtering considers neighbor pixels at the borders. When your neighbour pixels are i.e. black, you will get an ugly line. The effect will increase with mipmapping, that is, when decreasing the screen resolution or moving father away lower mipmaps will be taken, which result in an more obviously border.

The best solution for skyboxes are cubemaps, as mhagain already said.