cat efficiency below threshold means one of the following:
-cat is bad, not being as effective as required at reducing emissions. most likely if your cat is really bad, you'd have a bad stink coming from the tail pipe (people say it's like rotten eggs).
-or, a post-cat o2 sensor is fouled, meaning that the computer is getting a reading that makes it think your cat efficiency is bad. you can find which sensor it is by tracing the exhaust manifold back from cylinders 1-3, and finding the post-cat sensor on that side.
in my owner's manual, it says o2 sensors should be changed every 90k miles. so if they haven't been changed yet and your miles are up there, go ahead and do it. you can use a box wrench; i changed all 4 of mine using a box wrench.
pre-cat and post-cat sensors are the same, except one of them has longer wires (i think the pre-cat are longer wires). the place i ordered mine from just sends the pre-cat sensors no matter which are ordered. i think most places now do that, they just stock the ones with the longest wires.
also, as far as o2 sensors, the pre-cat ones are critical for your engine to run properly. the post-cat sensors merely monitor the cat efficiency, and were installed as a result of obdII requirements. if your post-cat sensors, or even your cats are bad, it shouldn't effect the operation of your engine. they are merely for environmental reasons. so you wouldn't pass an inspection with them bad, but if you don't have time/money/desire to fix it now, you can always do it before your next inspection.
-- the above is copied and pasted from another bmw forum.