Octavia MK2 1.6 FSI error P0420

Hello guys, I have an Octavia MK2 1.6 FSI 2005 with 121000 miles and now I'm getting the EML on, and on the reader it says P0420 - P0420 Catalyst System Efficiency Below Threshold.
The engine is vibrating a bit on idle compare to normal days (before the error came up), and I'm feeling a little bit of hesitation when accelerating. I mention I just changed 2 days ago the Ignition Coils for Cylinder 2 and 4, as they were gone (the engine was running like crap, no power, shaking and juddering a lot). I suppose there are 2 Lambda sensors, are they difficult to replace ? 

I don't know if the sensors  were changed before, as I have the car for 1 year now, but I'm thinking if it's not a connection with recent change of Ignition Coils for Cylinder 2 and 4. Also what else can it be ? Fuel injector ? Fuel filter ? The thing is this error is a bit too generic, and I don't want to be in a position of changing the O2 sensors and find out it's something else..

Any opinion would be much appreciated..