Hi !
I had the same problem on my GF's car, a Mazda Protege 2002 LX with 2.0L engine (canadian).
Codes P0300 & P0421. Also, the car was sometimes having trouble to keep idle and also sputtering, but it was not always. Also sometimes at high speed, the car would just not accelerate even at WOT.
I changed the spark plugs because they where due.
And also I bought 2 coil pack from the scrap yard and changed tem., No more Code P0300 random misfire and I unplug the 1st O2 sensor, and the code changed, repluged it and the P0421 came back. But the car goes well.
I will change the Upper O2 sensor and I'm pretty sure it will fix the problem. I'll keep you informed on further answers.
Thanks to this forum, it helped a lot !