I tried to fix his by reinstalling it completely.
I used following commands:
sudo apt-get autoremove gnome-do
sudo apt-get install gome-do

The problem does remain, unfortunately:

[1004] 2009-01-21 09:11:45 (~)
% sudo apt-get autoremove gnome-do
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following packages were automatically installed and are no longer required:
  libevolution3.0-cil libwnck2.20-cil libnotify0.4-cil
  libgnomedesktop2.20-cil
The following packages will be REMOVED:
  gnome-do gnome-do-plugins libevolution3.0-cil libgnomedesktop2.20-cil
  libnotify0.4-cil libwnck2.20-cil
0 upgraded, 0 newly installed, 6 to remove and 0 not upgraded.
After this operation, 3273kB disk space will be freed.
Do you want to continue [Y/n]? y
(Reading database ... 141177 files and directories currently installed.)
Removing gnome-do-plugins ...
Removing gnome-do ...
Removing libevolution3.0-cil ...
Removing libevolution3.0-cil from Mono
Removing libgnomedesktop2.20-cil ...
Removing libnotify0.4-cil ...
Removing libnotify0.4-cil from Mono
Removing libwnck2.20-cil ...
Processing triggers for man-db ...
[1005] 2009-01-21 09:12:40 (~)
% sudo apt-get install gnome-do
Reading package lists... Done
Building dependency tree
Reading state information... Done
The following extra packages will be installed:
  gnome-do-plugins libevolution3.0-cil libgnomedesktop2.20-cil
  libnotify0.4-cil libwnck2.20-cil
Suggested packages:
  epiphany-browser monodoc-gtk2.0-manual
The following NEW packages will be installed:
  gnome-do gnome-do-plugins libevolution3.0-cil libgnomedesktop2.20-cil
  libnotify0.4-cil libwnck2.20-cil
0 upgraded, 6 newly installed, 0 to remove and 0 not upgraded.
Need to get 1020kB of archives.
After this operation, 3273kB of additional disk space will be used.
Do you want to continue [Y/n]?
Get:1 http://be.archive.ubuntu.com intrepid/universe libgnomedesktop2.20-cil 2.20.1-2ubuntu4 [17.6kB]
Get:2 http://be.archive.ubuntu.com intrepid/universe libnotify0.4-cil 0.4.0~r2998-1 [9018B]
Get:3 http://be.archive.ubuntu.com intrepid/universe gnome-do 0.6.1.0-0ubuntu2 [180kB]
Get:4 http://be.archive.ubuntu.com intrepid/universe libevolution3.0-cil 0.17.5-0ubuntu1 [91.9kB]
Get:5 http://be.archive.ubuntu.com intrepid/universe libwnck2.20-cil 2.20.1-2ubuntu4 [37.8kB]
Get:6 http://be.archive.ubuntu.com intrepid/universe gnome-do-plugins 0.6.0.1+dfsg-0ubuntu2 [683kB]
Fetched 1020kB in 1s (963kB/s)
Selecting previously deselected package libgnomedesktop2.20-cil.
(Reading database ... 140985 files and directories currently installed.)
Unpacking libgnomedesktop2.20-cil (from .../libgnomedesktop2.20-cil_2.20.1-2ubuntu4_i386.deb) ...
Selecting previously deselected package libnotify0.4-cil.
Unpacking libnotify0.4-cil (from .../libnotify0.4-cil_0.4.0~r2998-1_all.deb) ...
Selecting previously deselected package gnome-do.
Unpacking gnome-do (from .../gnome-do_0.6.1.0-0ubuntu2_i386.deb) ...
Selecting previously deselected package libevolution3.0-cil.
Unpacking libevolution3.0-cil (from .../libevolution3.0-cil_0.17.5-0ubuntu1_i386.deb) ...
Selecting previously deselected package libwnck2.20-cil.
Unpacking libwnck2.20-cil (from .../libwnck2.20-cil_2.20.1-2ubuntu4_i386.deb) ...
Selecting previously deselected package gnome-do-plugins.
Unpacking gnome-do-plugins (from .../gnome-do-plugins_0.6.0.1+dfsg-0ubuntu2_all.deb) ...
Processing triggers for man-db ...
Setting up libgnomedesktop2.20-cil (2.20.1-2ubuntu4) ...
Setting up libnotify0.4-cil (0.4.0~r2998-1) ...
* Installing 1 assembly from libnotify0.4-cil into Mono

Setting up gnome-do (0.6.1.0-0ubuntu2) ...

Setting up libevolution3.0-cil (0.17.5-0ubuntu1) ...
* Installing 1 assembly from libevolution3.0-cil into Mono

Setting up libwnck2.20-cil (2.20.1-2ubuntu4) ...
Setting up gnome-do-plugins (0.6.0.1+dfsg-0ubuntu2) ...
[1006] 2009-01-21 09:13:18 (~)
% gnome-do

Unhandled Exception: System.InvalidOperationException: Could not read add-in description
  at Mono.Addins.Addin.get_Description () [0x00000]
  at Mono.Addins.AddinSessionService.CheckHostAssembly (System.Reflection.Assembly asm) [0x00000]
  at Mono.Addins.AddinSessionService.ActivateRoots () [0x00000]
  at Mono.Addins.AddinSessionService.Initialize () [0x00000]
  at Mono.Addins.AddinManager.Initialize (System.String configDir) [0x00000]
  at Do.Core.PluginManager.Initialize () [0x00000]
  at Do.Do.Main (System.String[] args) [0x00000]
[1007] 2009-01-21 09:13:27 (~)
% sudo apt-cache policy gnome-do
gnome-do:
  Installed: 0.6.1.0-0ubuntu2
  Candidate: 0.6.1.0-0ubuntu2
  Version table:
 *** 0.6.1.0-0ubuntu2 0
        500 http://be.archive.ubuntu.com intrepid/universe Packages
        100 /var/lib/dpkg/status
[1008] 2009-01-21 09:25:00 (~)
%