I am getting small amounts of water in my basement after large quantities of rain. I think the issue is related to a slight negative slope around part of the foundation where water is seeping in. I want to try to build the slope up around this area that has a mulch bed about 25'x5'. Should I dig out the old mulch before trying to regrade with a few yards of soil? I'd estimate a few inches of mulch in the area at question.
I think you should, because the mulch is going to let water pass right through it. It will be better if you remove the mulch, regrade the soil so that you have at least a 1/4" per foot drop moving away from the house and pack the soil to encourage the water to deflect away from the house. Then the mulch can go back on top and water passing through will be slowed down by the mulch (preventing erosion) and run off the soil away from the house.
How is the water getting in the basement? Through a window well, for example? If that is the case then regrading alone would do the job. Your friend in this matter is 4 inch diameter drain pipe with sleeve buried 3 to 8 " deep parallel the the side of the house experiencing the issue. Then proper grading with soil or even flagstone will cause the water to run off.
As other posters suggest mulch is not what you want against the foundation unless it is impermeable like pea stone.
However if you have a small crack in your foundation then more serious work is in order before the landscaping. Foundation issues must be addressed first, good grading is the final touch.
EDIT: the original poster asks about how to diagnose severity in foundation cracks. A standard construction technique is a poured concrete foundation with a skim coat of concrete at the ground level called parging. A crack in the parging is not going to cause a leak in a poured foundation. However, other foundations are built of concrete block which is inherently porous at the joints. Parging can assist here in preventing water from coming in contact with the joins in the blocks that are at ground level.
More to the point, can you see a crack in your foundation on the inside? If you can then you need to fix it first. Grading and mulch come after this is fixed. If you believe that an exterior crack is just in the parging then this can be fixed with some patch or grout mortar and a trowel.
I also note that waterproofing and foundation issues are not my area of expertise and my comments above are based on my experience as a homeowner. Consult a professional if your water issues are causing property damage.