Choosing a minimal covering while avoiding "bad" subsets. $\newcommand{set}[1]{\left\{#1\right\}}$
Let $S$ be a set and $\mathcal B\subseteq \mathcal P(S)$ a collection of subsets; we will call $B\in \mathcal B$ a bad subset of $S$. We further assume all bad subsets $B$ have $|B|>1$.
Suppose $\mathcal C\subseteq \mathcal P(S)$ is a covering of $S$; that is, $S=
\bigcup_{C\in\mathcal C} C$. We say a subset $T\subset S$ is good if $B\not\subset T$ for any $B\in \mathcal B$; that $\mathcal C$ is good if any $C\in \mathcal C$ is good; and that $\mathcal C$ is minimal good if $|\mathcal C|$ is minimal among all good coverings of $S$. 
For example, if $S=\{a,b,c\}$ and $\mathcal B=\{\{a,b\},\{b,c\}\}$, the singleton set $\{\{a\},\{b\},\{c\}\}$ is a good covering, and $\{\{a,c\},\{b\}\}$ is the unique minimal good covering. However, if $S=\{a,b,c,d\}$ and $\mathcal B=\{\{a,b\},\{c,d\}\}$, then both $\{\{a,c\},\{b,d\}\}$ and $\{\{a,d\},\{b,c\}\}$ are minimal good coverings.
Question: Given $S$, $\mathcal B$, is there a straightforward way to generate a minimal good covering, either directly or with an efficient algorithm? 
(Or put another way: how can we generate a minimal collection of sets which dominate all subsets (in the inclusion partial order) except those which are supersets of a particular collection of sets.)
Naively, this requires searching $\mathcal P(S)$, so is exponential in $|S|$. Some observations: 


*

*If there is a subset $X\subset S$ such that either $X\subseteq B$ or $X\cap B=\emptyset$ for all $B\in \mathcal B$, then we can quotient out by $X$ (i.e. identify those elements) and solve the problem for $S'$, where $|S'|=|S|-|X|+1$.

*If we can find a maximal good set; that is, a good set $T\subset S$ such that $|T|$ is maximal with this property; then if $\mathcal C'$ is a minimal good covering of $S-T$, $\mathcal C'\cup \{T\}$ is a good covering of $S$. However, it may not be minimal: e.g. if $S=\set{a,b,c,d,e}$, and $B=\set{B\subset S\mid |B|\geq 4}\cup\set{\set{a,b}}$, then $T=\set{c,d,e}$ is maximal good, and $\mathcal C'=\set{\set{a},\set{b}}$.
However, it is easy to see that $\set{\set{a,d,e},\set{b,c}}$ is a minimal good covering.
Edit (for posterity): This problem is equivalent to finding a minimal hypergraph coloring, which, as the answer notes, includes graph coloring as a subcase.
 A: Edit: After an embarrassing faulty answer, I produced an answer (kept below) which is correct but grossly much too difficult. Actually the reduction is almost trivial.
Your problem is NP-complete, because graph coloring is a special case of it. Note that for a good cover, we can without loss of generality take all its elements to be disjoint, because we can just take elements away from sets if they are already in other sets.
Now let $G = (S, B)$ be a graph. Then your problem is exactly the problem of determining the chromatic number of a graph.

Unfortunately (?), your problem is NP-complete. 
That it is in NP is clear, so let us show it is NP-hard. Suppose we can solve your problem efficiently, and let us show that we can also solve the 3-dimensional matching problem efficiently. Specifically, we will prove that we can decide whether there exists a perfect 3D matching if we could solve your problem efficiently. Even this problem is NP-complete, as is noted in the "Decision Problem" part of the Wikipedia page.
Let $X, Y, Z$ be sets of equal cardinality $k$, and let $T \subseteq X \times Y \times Z$. (We will gloss over the distinction between a tuple $(x, y, z)$ and the set $\{x, y, z\}$.) We want to decide whether we can take $k$ elements from $T$, so that each element from $X, Y, Z$ appears in one of the $k$ elements. Now let $S = X \sqcup Y \sqcup Z$, and let $B$ consist of all two-element subsets of $X$, all two-element subsets of $Y$, all two-element subsets of $Z$, and all elements of $X \times Y \times Z \setminus T$. Note that the cardinality of $B$ is polynomial in $k$.
With this $B$, a good cover for $S$ contains only subsets of at most 3 elements, and any 3-element subset it contains must be an element of $T$, since all other 3-element subsets are in $B$. Thus, if a good cover has $k$ elements, which is minimal, it must consist of only 3-element subsets, and hence be a perfect 3D matching. Conversely, a perfect 3D matching is clearly a good cover with $k$ elements.
Hence, there is a $k$-element perfect cover for this set if and only if there is a perfect 3D matching in our 3D matching problem.
