Android - What does the voice privacy setting do?

This is a feature of CDMA (standardized in IS-95) and is called Voice Privacy.

See an Analysis of IS-95 CDMA Voice Privacy by M.Zhang, et al. from 2000, free download here

Citation (the real paper begins at p.10 in the PDF:
Abstract. The voice privacy of IS-95 CDMA cellular system is analyzed in this paper. By exploiting information redundancy on the downlink traffic channel, it is shown that an eavesdropper can recover the voice privacy mask after eavesdropping the transmission on the downlink traf- fic channel for about one second. Thus, IS-95 CDMA voice privacy is vulnerable under ciphertext-only attacks.

That cryptanalysis is now 12 years old and already then was the scheme considered broken. I guess it's easy to suggest to just leave the setting disabled.

By combining some information grepped from the android source, I'm pretty sure it's what you're asking for.

To make it a little more transparent here are some source references:

packages/apps/Phone/res/xml/cdma_call_privacy.xml defines:

<?xml version="1.0" encoding="utf-8"?>
<PreferenceScreen xmlns:android="http://schemas.android.com/apk/res/android"
        xmlns:settings="http://schemas.android.com/apk/res/com.android.phone"
        android:title="@string/additional_cdma_call_settings">

    <com.android.phone.CdmaVoicePrivacyCheckBoxPreference
        android:key="button_voice_privacy_key"
        android:title="@string/voice_privacy"
        android:persistent="false"
        android:summary="@string/voice_privacy_summary"/>
</PreferenceScreen>

packages/apps/Phone/res/values/strings.xml defines those strings:

<string name="voice_privacy">Voice Privacy</string>  
<string name="voice_privacy_summary">Enable enhanced privacy mode</string> 

./hardware/ril/include/telephony/ril.h defines also:

typedef struct {
    RIL_CallState   state;
[...]
    char            isVoice;    /* nonzero if this is is a voice call */
    char            isVoicePrivacy;     /* nonzero if CDMA voice privacy mode is active */
[...]
} RIL_Call;

Voice Privacy is something that is part of CDMA. I found this article that talks a little bit about it in the introduction.

Voice privacy of IS-95 CDMA is provided by means of the long code mask.The long code mask is not transmitted through any channel, it is constructedby the base station and the mobile station. To recover the long code sequence,the eavesdropper may exhaustively search the 42-bit long code mask, with atime complexity of O(2 42 ). This attack is viable but is hard to implement inreal time. Alternatively, it can be shown that the long code sequence can also be recovered if the eavesdropper can obtain 42 bits of plaintext-ciphertext pairs.As there are many mobile stations transmitting simultaneously on the tra cchannel and each mobile station only transmits approximately 3 minutes onthe average, it is rather di cult to obtain 42 bits of the plaintext message.

I have also found a couple posts that talk about how sprint did studies that said it isn't really any more secure, unless your eavesdropper has tons of money to spend on decrypting your call.

Actually, voice privacy on CDMA is an added layer of voice encryption. Sprint did some independent research (I've heard quotes as big as a million dollars worth) and determined that CDMA without Voice Privacy is just as secure (unless you've got a million dollars worth of financing to break into an individual phone call)...

In other words, turn the feature off, and don't worry about it.

From the My HTC EVO 3D book:

Touch to enable voice privacy, which makes your EVO 3D encrypt your phone calls.

What is Voice Privacy?

When you enable Voice Privacy, your EVO 3D starts encrypting your calls so nobody can eavesdrop on them. ... By encrypting your phone calls between your EVO 3d and the cell tower, you add an extra layer of protection on your calls just in case someone wants to try to listen in. For this feature to work, your cellular service provider must support it, otherwise enabling it on your EVO 3D is useless.