I have the same problem with Natty and whatever network I use... so evolution becomes totally unusable.

the output of nmcli:

david@david-pc:~$ nmcli -p nm
======================================================================================
                               Estado de NetworkManager
======================================================================================
EJECUTANDO      ESTADO          HARDWARE-WIFI   WIFI       HARDWARE-WWAN   WWAN      
--------------------------------------------------------------------------------------
ejecutando      conectado       desactivado     desactivado activado        desactivado


david@david-pc:~$ nmcli -p con
===============================================================================================================================
                                                     Conexiones de sistema
===============================================================================================================================
NOMBRE                    UUID                                   TIPO              ALCANCE  SELLO DE TIEMPO-REAL              
-------------------------------------------------------------------------------------------------------------------------------
Auto eth0                 cecbcde6-e097-4e5c-9582-a0bdc886732c   802-3-ethernet    sistema  sáb 02 jul 2011 00:48:46 CEST     
===============================================================================================================================
                                                     Conexiones de usuario
===============================================================================================================================
NOMBRE                    UUID                                   TIPO              ALCANCE  SELLO DE TIEMPO-REAL              
-------------------------------------------------------------------------------------------------------------------------------
Conexión cableada 1       ee473aa8-7373-43ab-9d1f-5e431abf5167   802-3-ethernet    usuario  nunca                             
....                      ac41f01a-caa8-4c75-8a44-092a66ba3810   802-11-wireless   usuario  sáb 02 jul 2011 00:16:19 CEST     
Auto IntranetWorkWiFi ed84b1a0-0757-47cb-aed2-e09f9ce6ca50   802-11-wireless   usuario  nunca                             
Work lan                   56b6af71-26ed-4d56-8d3a-d793e5ec49dc   802-3-ethernet    usuario  vie 01 jul 2011 17:32:39 CEST     


david@david-pc:~$ nmcli -p dev
===========================================
        Estado de los dispositivos
===========================================
DISPOSITIVO TIPO              ESTADO       
-------------------------------------------
wlan0      802-11-wireless   no disponible
eth0       802-3-ethernet    conectado    


The output of evolution:
david@david-pc:~$ evolution

(evolution:4156): GLib-GObject-CRITICAL **: Object class EMFolderTree doesn't implement property 'paste-target-list' from interface 'ESelectable'

(evolution:4156): GLib-GObject-CRITICAL **: Object class EMFolderTree doesn't implement property 'copy-target-list' from interface 'ESelectable'
evolution-mail-Message: Error occurred while existing dialogue active:
Para completar esta operación debe estar trabajando conectado a la red


Using evolution version 2.32.2-0ubuntu7.

If you need something more please let me know and I'll do whatever I can.

Thanks,
David