You say that you have recently replaced the beer lines, but have you ever replaced the gas lines? Even with a backflow-prevention valve on the regulator or manifold, it is still possible for a small amount of beer to 'burp' back into the gas line if you hook it up under pressure and it is quite full.
I had a series of kegs go sour on me, and solved the issue by replacing my gas lines. It couldn't hurt...