When is a Utility Knife to be preferred over a Chef's or a Paring knife? A Utility knife is a kitchen knife that is midway in size between a Chef's knife and a Paring knife. 

Although I own a Utility knife, I don't believe that I have ever used it except when my Chef's knife was unavailable. I took a look around to see what uses I might have missed. Wikipedia says (without citation) that this knife is "derided as filler for knife sets" which squares with my experience. A few links call this type of knife a Sandwich knife because it is, ostensibly, good for cutting sandwich cheese and meat. Here's what one source says:


  The utility knife is good for cutting larger vegetables and sandwich
  meats that are not large enough for a chef's knife


I have a hard time swallowing this because, whether I'm chopping very small items, say Kaffir lime leaves, or large vegetables, say an aubergine, the Chef's knife still feels most comfortable in my hand.

Can someone help me picture a legitimate use for this knife where a Chef's knife or Paring knife wouldn't do better?
There's no question that a 4 or 5 inch utility knife is going to see a lot less use than your chef's knife or your paring knife, both of which have innumerable uses.  The utility knife is a lot more specific, really being for cases where the paring knife is too short and the chef's knife is too heavy or thick.  I have a 4" utility knife, which (of course) I got for free with a 6" Sabatier chef's knife.  It gets used a couple times a week, for:


scoring onions in order to mince them
cutting limes in half (a chef's knife seems like overkill here)
splitting small peppers
slicing large California shallots
cutting cheese


... and similar occasional, accessory uses.  

Part of the problem with the 4" utility knife is that it's really a dwarf 6"-8" utility knife.  The 6" or 8" utility knife, now commonly called a "vegetable knife", is far more useful; the long, thin blade is excellent for making paper-thin vegetable and fruit slices, and can be used as a fileting knife if you don't have one.  At the 4" size, though, the utility knife is useful only for cutting things which happen to be small, and only if you don't already have a more general knife dirty.

If what you're really asking is "can I get rid of this knife?", the answer is "yes".