That message means that the O2 sensors, front and rear, cannot confirm clean burning engine.
Most shops will tell you that your Cat is distroyed and you will need two O2 sensors to boot!

I say use minimum 89 octane. If you currently use regular, fill the tank with premium to bring the tank up to 89 octane. The use of 87octane will cause the engine to knock; the knock sensors will inform the ECU/ECM and your timing will be retarded and additional fuel will be used to cool the piston chambers to stop the knocking.
This additional fuel is probably not burned completely and winds up in the cat. Too much of a bad thing is not good for your car.
If you look at the price of gasoline, 89 octane is 10 cents/gallon more than 87 octane, and 91/92/93 octane is 20 cents more than "regular". After you fill an empty tank with 18 gallons of fuel, multiply the 18 gallons by 10 or 20 and calculate how much more good gasoline costs compared to junky regular : $1.80 or $3.60 - per tankful! Whoopdeedo. One cup of Starbuck's coffee!!!

Klaus
--
I still miss my 164 and my 854T. Just driving a V70R :)