Do you know if the replacement camera was working or was it purchased new? Using known-good parts is important for troubleshooting and "new" cameras don't all work either.
With a complete reset of your device, I highly doubt it's a software issue. If you can get your hands on a known-good camera, that will help you determine if the problem is with the camera or the logic board (which is what I suspect). Have you dropped your phone recently or has it been repaired or come into contact with water?