I would say it's worth getting a Tech 2 or a ELM code reader on it and having a look at the live data, specifically the fuel trim values, and lambda sensor behaviour, to see what's going on.
The new exhaust could be affecting the fuel trims by virtue of being more or less free-flowing but I wouldn't expect it to be significant enough to put the EML on. If there are air leaks upstream of the main lambda sensors, or induction air leaks, fuel system problems, etc. this would be much more significant. That this occurred exactly when the exhaust was changed is a bit of a coincidence but if the fuel trims were already just below the limits maybe the slight effect the new exhaust had has pushed them over the limits.
The fact that both banks are complaining makes me think it's something common to both - fuel supply or air leaks.
I wouldn't expect this to be related to the post-cat lambda sensor relocation because they have no input to the fuel trim, they are for monitoring cat performance only.
Kevin