Truth be told, just about any case has potential to mess with the flash, even if it doesn't cover it or the camera lens. If there's anything even anywhere near the back of the phone, remove it and try again.
Is this a black, or a white iPhone?
Does it seem to make a difference if you take short / long range shots?
If you gently squeeze near the camera and flash (say just underneath as you take your snap), does it seem to help?