There is a way to check if your texture was loaded correctly but it's pretty much a simple hack. After calling glTexImage2D() and creating the texture, you can then read that texture's width or height and see if it's the correct value. If it's 0 (or was it -1?), that means it failed to load. Hacky, but it might be worth putting it into your Texture class to avoid the same problem again, especially on Android since it's only run at load time and of course almost free anyway.
GL_INVALID_VALUE is generated if you try to use a width/height greater than GL_MAX_TEXTURE_SIZE. I think you are thinking of GL_PROXY_TEXTURE_2D.
The idea is that GL_MAX_TEXTURE_SIZE is a rough estimate, since you may be using different format and type parameters. So you can more safely check by loading a proxy texture first; then read back the width or height values with glGetTexLevelParameter -- if zero, it means the texture will fail.
Easiest thing to do is just ensure your textures are a reasonable size, no larger than GL_MAX_TEXTURE_SIZE.
LibGDX might have a utility for this already, but if not:
IntBuffer buf = BufferUtils.newIntBuffer(16);
int maxSize = buf.get();
I've packed all my backgrounds into 2 different images now, which are combined in an atlas-file. You're saying it won't give me much of a boost, which makes sense when the images are so big. The 2 packed images use up about 200kb more space than the separated background images (probably because of the extra transparent space), so is the minimal boost enough to merit this minimal increase in bulk?
At the expense of startup time (should be pretty speedy), you could pack your textures together on the fly. I believe LibGDX includes this in one of their TexturePacker utility classes.