@Ticker -- Diann, I have black walnut trees in my yard. I actually posted a article here on ATP with a list of things that I have been able to grow under or near them. As far as shrubs go, I have a couple types of hydrangea, arborvitae, sambucus, a Tiger Eye sumac, and I just planted a boxwood within the root zone. Roses will grow there too, but my yard is too shady for them to thrive. Also kerria japonica would work, and I think that would look great with hostas. I have been looking for one of those but I will have to find it online, as they are not available locally.
