Override pluggable functions in a plugin?

WordPress has a file called pluggable.php which contains a list of functions you can override in your plugin.

The problem I am facing (I am overriding wp_authenticate) is for each blog in my network I try to activate this plugin, I get:

failure, can’t re-declare wp_authenticate which was previously declared in pluggable.php

This somewhat defeats the ease of use, I have to comment the function in the plugin file, activate the plugin, un-comment the function for it to work properly.

What is the correct way to do it?
Can’t expect users who download plugin to do all that.

I am using 3.5 + multi-site configuration

Wrap your function in if( ! function_exists( 'wp_authenticate' ) ) to get rid of the error and successfully activate your plugin:

if( ! function_exists( 'wp_authenticate' ) ){
    function wp_authenticate(){}
}

This is necessary because in the context of activating a plugin, the function does already exist, only after it is activated will your plugin load first and override the original in pluggable.php. Plugins are activated in a sandbox to capture any fatal errors which may prevent activation and successful recovery to a working state.