Why won't my beans soften?
Soaking beans will not soften them.  If done for a very long time (i.e., days), some beans will eventually begin to sprout or ferment, at which point they will become softer.  But that is generally not desirable for basic cooking.

Instead, you'll need to cook the beans to get them to soften.  Bring to a slow boil and then simmer until the interior is the desired texture.  (A common test is to take a few beans out on a spoon and blow on them; if the outside of the bean breaks open a bit when you blow, they are likely soft and cooked through.)

By the way, the main purpose of soaking is to hydrate the seed coat (the outer covering of the beans).  Once that happens, the moisture can more easily penetrate the interior when cooked, allowing the beans to soften.  If you don't soak, you'll simply waste the first part of your cooking hydrating the seed coat.  Depending on the type of beans, their age, and other factors, that could increase your cooking time by anywhere from 15 minutes to an hour or so.  (For more details, see my previous answer to another question here.)

Also, do NOT try using an acid.  Acids can actually toughen the seed coat, making the beans take longer to cook and soften.  This is one of the reasons chili recipes (for example) often recommend cooking the beans first, before adding to acidic ingredients like tomatoes.

(Note that cooking times for beans and lentils can vary significantly, depending on type of bean and age.  For a mixed bean soup, I'd expect about 1-2 hours of simmering for pre-soaked beans, and perhaps as many as 3 hours.  Older beans can take longer, and I've occasionally had old batches of dried beans which never quite softened to a consistent texture.)

EDIT: Just to add onto Joe's great advice from the Dry Bean Council, Harold McGee has this to say about beans which never soften (from On Food and Cooking):


  "Hard-to-cook" beans... are normal when harvested, but become resistant
  to softening when they're stored for a long time -- months -- at warm
  temperatures and high humidities.  This resistance results from a
  number of changes in bean cell walls and interiors, including the
  formation of woody lignin, the conversion of phenolic compounds into
  tannins that cross-link proteins to form a water-resistant coating
  around the starch granules.  There's no way to reverse these changes
  and make hard-to-cook beans as soft as regular beans.  And there's no
  way to spot them before cooking.  Once cooked, they're likely to be
  smaller than normal and so may be picked out before serving.


McGee also mentions that occasionally you may encounter batches of "hard-seed" beans, which hardened during particularly hot and humid growing conditions.  In such cases, the beans will be tough no matter how early they are used; they may take much longer to cook than usual (and sometimes may never soften).