On www.wpmu.be I have the next code inserted in CSS:

.widget ul li a:link,
.widget ul li a:visited,
.widget ul li a:active,
.widget ul li a:hover {
border-left: 0 !important;
padding-left: 0 !important;
}

.widget ul {
list-style-type: none !important;
padding-left: 0;
margin-left: 0;
}

.widget ul li {
/* Background image instead of "list-style-type: image" because positioning is 
more precise and cross-browser safe. "0 3px" means 0px to the right, 3px to the bottom, 
starting in the top left corner of the <LI> element.  These numbers would be different with 
a different image and/or different text size. */
background: url(/wp-content/themes/atahualpa/images/icons/add-gray.gif) no-repeat 0 3px; 

/* [width of image = 12px] + [desired distance between icon and link text = 6px] = 18px */
padding-left: 18px; 

/* indent the icons a bit from the left */ 
margin-left: 2px; 

/* Overwrite the still active "display:block" for Firefox. 
This is usually not required, but required in Atahualpa */
display: list-item; 
}

/* OPTIONAL */
.widget ul li ul li {
/* Adjust the indention of 2nd level items. Without this, the indention of 2nd level 
items will be: [padding-left of 1st level LI = 18px] + [margin-left of 1st level LI = 2px]. 
We reduce this rather huge left indention by setting a negative left margin. The image 
being used here is a  tad too big for a bullet, the 18px padding-left is causing the sub 
items to be indented relatively far. With a smaller bullet image, and smaller padding-left, 
we could probably drop this last style altogether, the 2nd level indention would look o.k. */
margin-left: -5px; 
}

I tried to set the margin to 15 pixels in > Sidebars & Widgets > Style Widgets but this did not help? On www.incotrust.be I did the same and there it works fine! ??

See for yourself on www.wpmu.be the links are over the icons... strange thing is that the Icons are OK in the Widget of a plugin (in this case Count per day)

Now I used:

.widget ul li a:link,
.widget ul li a:visited,
.widget ul li a:active {
border-left: 0 !important;
padding-left: 13px !important;
background: url(/wp-content/themes/atahualpa/images/icons/add.gif) no-repeat 0 3px; 
}

.widget ul li a:hover {
/* leave out the next line if you want to keep the default black font color on hover, 
just showing you where you would change the hover font color */
color: #4177bb !important;
border-left: 0 !important;
padding-left: 13px !important;
background: url(/wp-content/themes/atahualpa/images/icons/add-gray.gif) no-repeat 0 3px; 
}

.widget ul {
list-style-type: none !important;
padding-left: 0;
margin-left: 0;
}

.widget ul li {
padding-left: 0px; 
margin-left: 0px; 
display: list-item; 
}

/* indent sub items a bit more */
.widget ul li ul li {
margin-left: 0px; 
}

This one works if I set the marges on 0

I'm confused, don't you mean the Category WIDGET and not the Category MENUBAR?

Yes sorry, the first code worked on incotrust.be but not on wpmu.be the second code worked on wpmu.be but I has to set the spacing of the links on 0, but it works now perfect with the second code!