Here is what works for me. 
First, the Broadcast:
@Override
public void onReceive(Context context, Intent intent) {
    if (intent.getAction().equals(Intent.ACTION_BOOT_COMPLETED)) {
        ComponentName service = context.startService(
                new Intent(context, ClipboardMonitor.class));
        if (service == null) {
            Log.e("TAG", "Can't start service");
        }
    } else {
        Log.e("TAG", "Recieved unexpected intent " + intent.toString());
    }
}
and then this is the service 
private MonitorTask mTask = new MonitorTask();
private ClipboardManager mCM;
@Override
public IBinder onBind(Intent intent) {
    return null;
}
@Override
public void onCreate() {
    mCM = (ClipboardManager) getSystemService(CLIPBOARD_SERVICE);
    mTask.start();
}
@Override
public void onDestroy() {
    mTask.cancel();
}
@Override
public void onStart(Intent intent, int startId) {
}
/**
 * Monitor task: monitor new text clips in global system clipboard and
 * new image clips in browser download directory
 */
private class MonitorTask extends Thread {
    private volatile boolean mKeepRunning = false;
    private String mOldClip = null;
    public MonitorTask() {
        super("ClipboardMonitor");
    }
    /** Cancel task */
    public void cancel() {
        mKeepRunning = false;
        interrupt();
    }
    @Override
    public void run() {
        mKeepRunning = true;
        while (true) {
            doTask();
            if (!mKeepRunning) {
                break;
            }
        }
    }
    private void doTask() {
        if (mCM.hasText()) {
            String newClip = mCM.getText().toString();
            if (!newClip.equals(mOldClip)) {
                mOldClip = newClip;
               // Toast.makeText(getApplicationContext(), "" +  newClip.toString(), Toast.LENGTH_SHORT).show();
                Log.i("TAG", "new text clip inserted: " + newClip.toString());
            }
        }
    }
Also, the permissions:
<uses-permission android:name="android.permission.GET_CLIPS" />
<uses-permission android:name="android.permission.READ_CLIPS" />
<uses-permission android:name="android.permission.WRITE_CLIPS" />
<uses-permission android:name="android.permission.RECEIVE_BOOT_COMPLETED" />
<service android:name=".ClipboardMonitor" />
<receiver android:name=".ClipboardMonitorStarter">
    <intent-filter>
        <action android:name="android.intent.action.BOOT_COMPLETED" />
    </intent-filter>
</receiver>