Thankfully, the phones (GSM mostly) will display icons that indicate the encryption is disabled and many customers will receive SMS messages indicating that this action is taking place. If you are visiting Russia, don't bother to make any confidential calls, because it's not just the Russian federal police that can listen to you, it's anybody with an appropriate scanner.
From the article, it appears that this isn't a particularly odd thing for the FSB to request. Encryption was shut down during the hostage crisis in the Moscow theater last year and was also turned off during the 300th anniversary celebration in St. Petersburg (which must have been a real pain for any visiting businesspeople).
Of course, in the US, the FBI wouldn't bother to request such a thing because most cellular communication isn't encrypted here anyway, unless you are using a GSM phone (T-Mobile, some AT&T, some Cingular, some Bell South).